The Idea: Build and Splice Closed Trails
An Euler circuit is a closed trail that uses every edge of a graph exactly once. In a connected undirected graph where every vertex has even degree, the challenge is not just to find a closed trail, but to ensure that no edges are left out. Hierholzer’s algorithm does this by first finding one closed trail and then inserting further closed trails wherever unused edges remain.
All graphs in this tutorial are finite, simple and undirected. A trail is a walk that does not repeat edges; it may repeat vertices. A circuit is a closed trail. We consider connected graphs with at least one edge in which every vertex has even degree. The one-vertex graph with no edges is a trivial exception: its length-zero walk is an Euler circuit, and no edge-search is needed.
The algorithm keeps track of which edges are unused. At any stage, a closed trail already found can be extended as a final circuit by splicing in another closed trail that starts at a vertex of the current circuit. The new trail uses only unused edges, so the splice adds edges without repeating any.
Hierholzer’s Algorithm
Choose a vertex incident to an edge and follow unused incident edges, never reusing an edge, until the trail returns to its starting vertex.
Inspect the vertices of the circuit. If every one has no unused incident edge, stop. Otherwise choose a circuit vertex with an unused incident edge.
Starting at that vertex, follow unused edges until the trail returns there.
Insert the new closed trail into the existing circuit at its starting vertex. Continue until no circuit vertex has an unused incident edge.
When making any choice, an implementation can fix an order for the incident edges and always take the first available one. The choice of order can change the circuit returned, but not whether the method succeeds. The key facts are that each new trail closes and that, if any edges remain, some vertex of the current circuit is incident to an unused edge.
Why the Trails Close
Proof. Let the trail start at \(s\) and currently end at \(v\ne s\). Among the edges used by this trail, the number incident to \(v\) is odd: every earlier arrival at \(v\) is paired with a departure, while the current arrival has not yet been paired with a departure. The total degree of \(v\) in the graph is even. Therefore the number of incident edges at \(v\) that have not been used is even minus an odd number, hence odd. Since a nonnegative odd number is at least \(1\), there is an unused edge at \(v\). Thus the trail cannot stop at \(v\ne s\). Because the graph has finitely many edges and no edge is used twice, the process must eventually stop; when it does, its endpoint must be \(s\). \(\square\)
The same argument applies after some closed trails have already been found. A closed trail uses an even number of incident edges at each vertex: each time it visits a vertex, arrivals and departures pair up. Consequently, after removing the edges of any collection of closed trails, every vertex still has even degree in the graph of unused edges. The lemma therefore guarantees that a new trail started at a circuit vertex with unused edges returns to that vertex.
Proof. First, the lemma shows that the initial trail closes, so it is a circuit. Whenever the algorithm starts another trail at a vertex of the current circuit, all previously used edges form a closed trail or a union of closed trails. Thus every vertex has even degree among the unused edges, and the lemma shows that the new trail also closes. Splicing closed trails at a shared vertex gives a closed trail: the walk follows the old circuit to that vertex, follows the new trail back to the same vertex, and then continues along the old circuit. The new trail uses only unused edges, so this splice introduces no repeated edge.
It remains to show that the algorithm cannot stop while edges remain unused. Let \(S\) be the set of vertices on the current circuit. If an unused edge is incident to a vertex in \(S\), the algorithm has not finished, by its stopping rule. Suppose instead that unused edges remain but none is incident to \(S\). Since the graph is connected and has an edge on the circuit, there is a path from a vertex in \(S\) to an endpoint of an unused edge. Along that path, take the first edge that leaves \(S\). It cannot be a used edge, because every used edge belongs to the current circuit and has both endpoints in \(S\). So it is an unused edge incident to \(S\), contradicting the supposition. Hence, if any unused edge remains, some circuit vertex has an unused incident edge and another trail can be spliced in.
Each round uses at least one previously unused edge, and there are finitely many edges. The algorithm therefore terminates. It terminates only when no circuit vertex has an unused incident edge; the preceding argument shows that this means no edges remain unused. The final closed trail consequently uses every edge exactly once, so it is an Euler circuit. \(\square\)
Worked Constructions
Worked Example: The Circuit of a 4-Cycle
Let \(G\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41\}\). Every vertex has degree \(2\), so the even-degree condition holds. Start at \(1\) and use the following available edges:
| Step | Edge used | Vertices so far | Unused edges |
|---|---|---|---|
| Start | — | \(1\) | \(\{12,23,34,41\}\) |
| 1 | \(12\) | \(1,2\) | \(\{23,34,41\}\) |
| 2 | \(23\) | \(1,2,3\) | \(\{34,41\}\) |
| 3 | \(34\) | \(1,2,3,4\) | \(\{41\}\) |
| 4 | \(41\) | \(1,2,3,4,1\) | \(\varnothing\) |
The trail returns to its start, and there are no unused edges to splice in. The output is \(1,2,3,4,1\). Check: its four consecutive edges are \(12,23,34,41\), exactly the four edges of \(G\), each appearing once. Independently, the degree sum is \(2+2+2+2=8=2|E|\), consistent with \(|E|=4\).
Worked Example: Splicing Two Triangles
Let \(G\) have \(V=\{a,b,c,d,e\}\) and \(E=\{ab,bc,ca,ad,de,ea\}\). The triangles \(a,b,c,a\) and \(a,d,e,a\) share the vertex \(a\). The degrees are \(\deg(a)=4\) and \(\deg(b)=\deg(c)=\deg(d)=\deg(e)=2\).
Start with \(a,b,c,a\), using \(ab,bc,ca\). There are then three unused edges: \(ad,de,ea\). The current circuit contains \(a\), which is incident to unused edges. Starting there, the unused trail \(a,d,e,a\) uses \(ad,de,ea\) and returns to \(a\). Splice it at the occurrence of \(a\) in the first circuit to obtain
Check: reading consecutive pairs gives \(ab,bc,ca,ad,de,ea\), which lists all six edges exactly once and returns to \(a\). The independent degree count is \(4+2+2+2+2=12=2\cdot6\).
Worked Example: Splicing at More Than One Vertex
Let \(G\) have \(V=\{1,2,3,4,5,6,7,8\}\) and \(E=\{12,23,34,41,35,56,63,27,78,82\}\). This consists of the 4-cycle \(1,2,3,4,1\), the triangle \(3,5,6,3\), and the triangle \(2,7,8,2\). The degrees of \(2\) and \(3\) are \(4\); every other vertex has degree \(2\). Thus all degrees are even.
First follow \(1,2,3,4,1\), using \(12,23,34,41\). The unused edges are \(35,56,63,27,78,82\). Vertex \(3\) on the circuit has unused incident edges, so follow \(3,5,6,3\) and splice it at \(3\). The circuit is now \(1,2,3,5,6,3,4,1\). Vertex \(2\) is still on this circuit and has unused incident edges. Follow \(2,7,8,2\) and splice at \(2\), giving the final circuit
Check: the consecutive edges are \(12,27,78,82,23,35,56,63,34,41\). These are exactly the ten edges in \(E\), each once, and the walk returns to \(1\). The degree sum is \(2+4+4+2+2+2+2+2=20=2\cdot10\), independently confirming the edge count.
Common Pitfall: Checking Only the Starting Vertex
In the last example, after the first trail \(1,2,3,4,1\), vertex \(1\) has no unused incident edge. It would be wrong to stop on that basis: the six edges \(35,56,63,27,78,82\) remain. The algorithm checks every vertex of the current circuit, not only its starting vertex. In this case the unused triangles attach at vertices \(3\) and \(2\), so they can be reached by splicing there.
A second point to keep straight is that an Euler circuit need not be a cycle: a cycle has no repeated vertices apart from its start and end, while an Euler circuit may revisit vertices. The final walk in the third example visits \(2\) and \(3\) more than once, but it never repeats an edge. The edge-use condition, not the vertex-use condition, is what makes it Eulerian.
Hierholzer’s method is useful whenever every edge must be included in one closed route. Its efficiency comes from postponing choices about how to combine routes: make any valid closed trail, find where unused edges meet it, and splice in more closed trails until none remain. The proof explains why this local procedure succeeds globally: even degrees force each new trail to close, and connectedness ensures that remaining edges cannot be separated from the circuit already built.
Check Your Understanding
For each question, justify the answer using the edge-splicing procedure or its proof.
- Why can a trail of unused edges in an even-degree graph not stop at a vertex other than its starting vertex?
- In the graph with \(V=\{a,b,c,d,e\}\) and \(E=\{ab,bc,ca,ad,de,ea\}\), what closed trail can be spliced into \(a,b,c,a\), and what circuit results?
- In the third worked example, why is it insufficient to check only whether vertex \(1\) has unused incident edges after the initial circuit is formed?
- Explain why splicing a closed trail into another circuit preserves the property that the resulting walk is closed.
- Which assumptions in the theorem are used to guarantee that the procedure uses every edge: even degrees, connectedness, or both? Explain each role.