From existence to construction
In Part 2, we learned how to determine whether an Eulerian path or cycle exists. The next question is practical: how do we actually construct such a traversal?
A naive idea would be to try all possible paths, but this quickly becomes inefficient. Fortunately, there is a simple and elegant method known as Hierholzer’s algorithm.
The key idea is to build the traversal incrementally, always following unused edges until we get stuck, and then integrating smaller cycles into a larger one.
High-level intuition
Imagine starting at any vertex (or at an odd-degree vertex if an Eulerian path is required). From there, follow edges one by one, never reusing an edge.
Because of the degree conditions, you will not get stuck prematurely. You will eventually return to the starting point (cycle case), or end at the second odd vertex (path case).
If there are still unused edges, it means that somewhere along your path, there exists a vertex with remaining edges. From that vertex, you can start a new traversal and later merge it into the main path.
Hierholzer’s Algorithm
The algorithm works as follows:
- Start at any vertex (or an odd-degree vertex if needed).
- Follow unused edges until you cannot continue.
- This produces a cycle (or a path segment).
- If unused edges remain, find a vertex in the current path with unused edges.
- Start a new walk from that vertex and merge it into the main path.
- Repeat until all edges are used.
The result is an Eulerian traversal that covers every edge exactly once.
Why does it work?
The correctness of the algorithm comes directly from the degree conditions. Every time we enter a vertex, there is another edge available to leave it (except possibly at the endpoints in the path case).
This ensures that partial walks can always be extended into cycles, and these cycles can be combined without breaking the structure.
The graph is gradually decomposed into cycles, which are then stitched together into a single traversal.
Complexity
Hierholzer’s algorithm is very efficient. Each edge is visited exactly once, and each operation is constant time.
Therefore, the total complexity is: \(O(E)\), where E is the number of edges.
This is optimal, since any algorithm must inspect every edge at least once.
Compared to Hamiltonian problems (which are often exponential), Eulerian construction is computationally simple.
Practical applications
Eulerian traversal algorithms are widely used in real systems:
- Route inspection (street sweeping, garbage collection)
- Network traversal and maintenance
- DNA sequencing and genome assembly
- Circuit design and PCB routing
In all these cases, the goal is the same: cover every connection exactly once with minimal redundancy.