Chapter 5 · Euler Tours and Hamilton Cycles
Euler Tours: When They Exist
Euler's degree condition, why it is both necessary and sufficient, and the directed/undirected split.
An Eulerian tour is a closed walk using every edge exactly once; an Eulerian trail (or path) uses every edge exactly once but need not be closed. Graphs admitting them are called Eulerian / semi-Eulerian.
A connected graph with at least one edge has
- an Eulerian tour ⇔ every vertex has even degree,
- an Eulerian trail from s to t ≠ s ⇔ exactly s and t have odd degree.
("Connected" means: connected after ignoring isolated vertices.)
(⇒) Each time a tour passes through v it consumes one in-arrival and one departure, contributing 2 to deg(v); a closed tour starts and ends at the same vertex, so even the start vertex gets 2 per visit plus a final closing. Hence all degrees even. For an open trail, the two endpoints are entered/left one extra time each — exactly the odd ones. (⇐) Induct on m. All degrees even ⇒ no vertex has degree 1, so some cycle C exists (walk until you repeat). Remove C: every degree stays even, and each component of G - C has fewer edges, so by induction each has an Euler tour. Splice: walk C, and whenever you enter a vertex of a component, detour along that component's tour and come back. All edges used exactly once. ∎
A digraph has an Eulerian circuit ⇔ (a) every vertex with nonzero degree lies in one strongly connected component of the underlying graph, and (b) deg+(v) = deg-(v) for all v. An Eulerian path s ⇝ t exists ⇔ deg+(s) = deg-(s)+1, deg-(t) = deg+(t)+1, all others balanced, plus the same connectivity condition.
Balance is necessary by the same pass-through argument (each visit uses one in-edge and one out-edge). For sufficiency, the balanced condition makes each weak component a union of directed cycles (take a maximal walk: it cannot get stuck except at the start, since every entry leaves an unused exit; so it closes). Then contract each cycle into one vertex — Contraction, Induction and Lifting rule 1 — and repeat: the component structure and balance are preserved, so the cycle graph of the decomposition can be spliced back together. Connectivity (a) is what lets you splice at all. ∎
Two disjoint directed cycles joined by a single arc x → y: degrees are unbalanced, so (b) already fails. But four cycles arranged as two balanced pairs, each pair internally strongly connected and joined one-way, passes balance everywhere and still has no tour. Always test reachability on the underlying graph and, in the directed case, that all nonzero-degree vertices are in one SCC (Strongly Connected Components).
#Deciding, then counting
Complexity of the Euler family
- decide existence: O(n + m) (degree scan + one DFS/SCC),
- construct: O(n+m) with Hierholzer (Hierholzer's Linear Algorithm),
- count Euler tours: #P-complete in general; for directed graphs the BEST theorem gives ∏v (deg+(v)-1)! · ec(G, r) where ec is the number of arborescences — an The Matrix–Tree Theorem determinant,
- minimum number of trails covering all edges of an undirected graph: max(1, #odd/2) — one line, follows from the parity argument above.