Euler path and circuit with conditions

Definitions

• Euler circuit: a closed walk that uses every edge of the graph exactly once, starting and ending at the same vertex.
• Euler path: a walk that uses every edge exactly once but starts and ends at different vertices.

Diagrams

Euler circuit (every vertex even):

   a         d
   |\       /|
   | \     / |       edges: ab, ac, bc, cd, ce, de
   |  \   /  |       degrees: c = 4, others 2
   |   \ /   |       circuit: c, a, b, c, d, e, c
   |    c    |
   |   / \   |
   |  /   \  |
   | /     \ |
   b         e

Euler path (two odd vertices):

 a ------- b
 | \       |        edges: ab, bc, cd, da, ac
 |   \     |        odd vertices: a, c (degree 3)
 |     \   |        path: a, b, c, d, a, c
 d ------- c

Necessary and sufficient conditions (connected undirected graph)

1. Euler circuit: exists if and only if every vertex has even degree.
2. Euler path (not circuit): exists if and only if exactly two vertices have odd degree. It must start at one odd vertex and end at the other.

Why necessary: each time the walk passes through a vertex it uses one edge to enter and one to leave, so the edges at each vertex pair up. Only the start and end of an open path can have odd degree. Why sufficient: when all degrees are even, a trail can only get stuck at its starting vertex, so it closes into a circuit; any unused edges form further closed trails, which can be spliced in to give one Euler circuit.

For directed graphs (connected): a circuit exists iff in-degree = out-degree at every vertex; a path exists iff one vertex has out − in = 1, one has in − out = 1, and all others are balanced.