Conditions for Euler circuits and paths

For a connected undirected graph:

• Euler circuit (closed walk through every edge exactly once): exists if and only if every vertex has even degree.
• Euler path (open walk through every edge exactly once): exists if and only if exactly two vertices have odd degree; the path starts at one of them and ends at the other.

Necessity: every time a walk passes through a vertex it uses two edges (one in, one out), so the edges at each vertex pair up. Only the starting and ending vertex of an open path can be left with an unpaired edge, so they alone may have odd degree. Since the number of odd-degree vertices in any graph is even, the possible counts are 0 (circuit) or 2 (path). Sufficiency is shown by building a circuit, or path, and splicing in closed trails over any unused edges.

For a directed graph: an Euler circuit exists iff the graph is connected and in-degree = out-degree for every vertex. An Euler path exists iff all vertices have in = out except one with out = in + 1 (start) and one with in = out + 1 (end).

Example: K₅ (all degrees 4) has an Euler circuit; K₄ (all degrees 3, four odd vertices) has neither.