Wait, What?
A graph can look tangled, yet if the degrees are right you can consume every edge exactly once without backtracking over the search space.
Hierholzer’s algorithm constructs an Eulerian circuit or trail by exploiting a structural promise: the graph already has the degree and connectivity conditions that make such a walk possible. The algorithm does not search among all possible paths. It consumes unused edges, closes cycles, and splices those cycles into one complete tour.
Quick Answer
Learn Hierholzer through Eulerian meaning → existence conditions → unused-edge invariant → cycle construction → stack/backtracking form → edge IDs → directed and multigraph cases → linear-time implementation → memory engineering. The central idea is that vertices are appended to the answer only when they have no unused incident edge left.
1. Eulerian Is About Edges, Not Vertices
An Eulerian circuit uses every edge exactly once and returns to its starting vertex. An Eulerian trail uses every edge exactly once but may start and end at different vertices.
Do not confuse this with a Hamiltonian path, which visits every vertex exactly once. Eulerian questions are governed by degree and connectivity and can be solved constructively in linear time. Hamiltonian existence is a fundamentally harder problem.
2. Check Existence Before Constructing
For an undirected graph, ignoring isolated vertices, all edge-bearing vertices must lie in one connected component. Then:
- Eulerian circuit: every vertex has even degree.
- Eulerian trail but not circuit: exactly two vertices have odd degree; they are the endpoints.
- No Eulerian trail: any other number of odd-degree vertices.
These tests are not optional decorations. If the graph is disconnected, perfect degree parity inside separate components still cannot produce one walk covering all edges.
3. Why You Cannot Get Stuck Too Early
In an Eulerian circuit graph, every time a partial walk enters a vertex along an unused edge, parity ensures there is another unused edge available to leave—until the walk returns to its starting point. This makes it possible to grow a closed cycle without needing global search.
If unused edges remain elsewhere, they must touch some vertex already on the current tour when the edge-bearing part of the graph is connected. Start another closed walk there and splice it into the first. Hierholzer’s original reasoning is essentially repeated cycle splicing.
4. The Stack Version Makes Splicing Implicit
Modern implementations usually avoid explicit list splicing. Keep a stack representing the current unfinished walk. From the top vertex, consume an unused edge and push the neighbour. If the top vertex has no unused edge left, pop it into the output. The output is produced in reverse completion order, so reverse it at the end.
hierholzer(start):
stack = [start]
trail = []
while stack is not empty:
v = stack[-1]
if v still has an unused incident edge (v, u):
mark that edge used
stack.append(u)
else:
trail.append(stack.pop())
reverse(trail)
return trailThe important invariant is: when a vertex is popped into the final sequence, every edge available from that visit has already been consumed. That is why completed pieces appear in the correct reverse order.
5. Trace One Example Slowly
Take two triangles sharing one vertex: A–B–C–A and A–D–E–A. Every degree is even. A walk may first consume the left triangle and return to A. Because A still has unused edges, the stack continues through the right triangle. Vertices are not committed to the final answer until their unused-edge lists are exhausted.
This trace is more valuable than memorising pseudocode. Record four columns: current stack, edge consumed, remaining degree, and output. Learners quickly see that “backtracking” here does not undo an edge choice; it finalises a vertex after its edges are finished.
6. Edge Identity Matters in Undirected Graphs
An undirected edge appears in two adjacency lists. If you only store neighbour names, it is easy to consume one direction and accidentally use the same physical edge again from the other endpoint. Assign each edge a unique ID and mark that ID used once.
adj[v] contains (u, edge_id)
used[edge_id] = false
when choosing (u, id):
if not used[id]:
used[id] = true
stack.append(u)Edge IDs also make parallel edges safe. Two edges between the same pair of vertices are distinct objects and must be traversed separately.
7. Avoid the Hidden O(E²) Trap
The mathematical algorithm is linear, but a careless container can destroy that bound. Repeatedly searching an adjacency list from the beginning for an unused edge may rescan the same entries many times. Deleting from the middle of an array can also be expensive.
Use a per-vertex cursor, or store adjacency in a structure from which the next edge can be popped in amortized O(1). With suitable adjacency representation, each edge is examined and consumed only a constant number of times, giving O(V + E) time including connectivity checks.
8. Open Trails Need the Correct Start
If an undirected graph has exactly two odd-degree vertices, start at one of them. The algorithm will finish at the other. Starting at an arbitrary even-degree vertex can cause a valid graph to produce a closed partial tour that does not represent the required open trail.
9. Directed Graphs Change the Degree Conditions
For a directed Eulerian circuit, each edge-bearing vertex must have equal indegree and outdegree, together with the appropriate connectivity of the directed edge-bearing structure. For an open directed trail, one start vertex has outdegree one larger than indegree, one end vertex has indegree one larger than outdegree, and all others balance.
The stack mechanism itself changes very little: consume only outgoing edges. The subtle part is validating the directed existence conditions correctly.
10. Professional Uses
- Route construction: tasks that must traverse every required connection once.
- de Bruijn graphs: sequence assembly and combinatorial sequence generation often reduce to Eulerian traversal.
- Chinese postman workflows: after odd-degree imbalances are repaired, Euler-tour construction is the final traversal step.
- Multigraph processing: edge IDs and multiplicities make Hierholzer especially natural.
11. A 2026 Professional Frontier: Working Memory
Classical implementations commonly keep a stack whose size can grow with the number of edges. A 2026 SIAM Symposium on Simplicity in Algorithms paper by Ismaili Alaoui, Plump and Wild presented a space-efficient Hierholzer variant that retains linear running time while reducing working memory for Eulerian cycles in multigraphs. Follow-up 2026 work studies the undirected read-only setting. This is a useful professional lesson: once asymptotic running time is optimal, representation and working-space models become the next engineering question.
12. How to Learn the Algorithm
Use a predict–trace–modify progression. First predict which vertex should be the start from the degree pattern. Then trace the stack and output by hand. Next modify one edge and explain how the existence condition changes. Only after that write code. Programming-education research on PRIMM, code tracing and subgoal-labelled examples supports this movement from reading and explaining execution toward independent construction.
Common Failure States
- Confusing Eulerian and Hamiltonian problems.
- Checking degree parity but not connectivity.
- Using neighbour pairs without unique edge IDs in an undirected multigraph.
- Marking only one adjacency-list entry and accidentally traversing the same edge twice.
- Starting an open Euler trail at an even-degree vertex.
- Rescanning adjacency lists and turning a linear algorithm into quadratic behaviour.
- Forgetting to reverse the pop-order output in the standard stack implementation.
- Assuming undirected degree rules apply unchanged to directed graphs.
Practice Ladder
- Beginner: classify small graphs as circuit, open trail or impossible.
- Foundation: trace the stack implementation on a graph with two cycles sharing a vertex.
- Intermediate: implement undirected Hierholzer with edge IDs and verify every edge appears once.
- Advanced: support directed graphs and multigraphs.
- Professional: benchmark cursor-based versus destructive adjacency representations and study the 2026 space-efficient variants.
- Verification: assert that a returned trail has exactly E+1 vertices for a nonempty undirected graph and that every edge ID is consumed exactly once.
Learning Hall Boundary
This article owns Eulerian trail/circuit construction with Hierholzer’s algorithm, including existence checks, edge-consumption invariants, stack implementation and multigraph engineering. It does not replace the Learning Hall’s general graph-traversal, shortest-path, matching, route-optimization, MindOS, Bolt or Student/Studying Interface canonical jobs.
Evidence Boundary
Current NetworkX documentation describes eulerian_circuit as a linear-time implementation and cites Edmonds and Johnson’s 1973 work on matching, Euler tours and the Chinese postman. The modern memory frontier is represented by Ismaili Alaoui, Plump and Wild, Space-Efficient Hierholzer: Eulerian Cycles in O(m) Time and O(n) Space, SOSA 2026. For pedagogy, the progression used here is informed by computing-education work on PRIMM, code tracing and subgoal-labelled worked examples.
Professional rule: you understand Hierholzer when you can prove why the walk cannot get stuck incorrectly, explain why pop-order is reversed, and preserve linear time in the actual data structure—not only in the pseudocode.
