Hierholzer Algorithm - Proof and Construction

Hierholzer's algorithm efficiently constructs Eulerian circuits in $O(m)$ time by building and merging cycles. We prove correctness and analyze the algorithm's elegant recursive structure.

TheoremHierholzer's Algorithm Correctness

For a connected graph $G$ where all vertices have even degree, Hierholzer's algorithm constructs an Eulerian circuit in time $O(m)$ where $m = |E|$ .

Proof

Algorithm:

EulerCircuit(G, start vertex v):
  circuit = []
  stack = [v]
  current_path = []

  while stack not empty:
    curr = stack.top()
    if curr has unused edges:
      next = neighbor via unused edge
      mark edge used
      stack.push(next)
    else:
      current_path.append(stack.pop())

  return reverse(current_path)

Correctness: We prove by induction that this constructs an Eulerian circuit.

Base case: If $G$ is a single cycle, the algorithm traces it completely.

Inductive step: Start at $v$ and follow unused edges until stuck. Since all degrees are even, when stuck at vertex $u$ , we must have $u = v$ (else $u$ would have odd unused degree). This forms a cycle $C$ .

If $C$ doesn't use all edges, since $G$ is connected, some vertex $w \in C$ has unused incident edges. The subgraph $H$ of unused edges has all even degrees (each edge in $C$ used exactly one edge at each endpoint). By induction, starting from $w$ constructs a circuit $C'$ in $H$ .

Merge: Insert $C'$ into $C$ at vertex $w$ . The result is an Eulerian circuit of $G$ .

Time complexity: Each edge is examined exactly twice (once for each endpoint). Stack operations are $O(1)$ . Total: $O(m)$ .

■

ExampleAlgorithm Execution

Consider a graph with vertices $\{1,2,3,4\}$ and edges forming two triangles sharing vertex 1: edges $(1,2), (2,3), (3,1), (1,4), (4,2), (2,1)$ .

Starting at vertex 1:

Follow $1 \to 2 \to 3 \to 1$ (first triangle)
At 1, still have unused edges to 4
Follow $1 \to 4 \to 2 \to 1$ (second triangle)
Merge at vertex 1: $1 \to 2 \to 3 \to 1 \to 4 \to 2 \to 1$

The algorithm naturally discovers and merges cycles.

DefinitionComparison with Fleury's Algorithm

Fleury's algorithm avoids bridges (cut edges) of the remaining graph:

Time: $O(m^2)$ (bridge detection at each step)
Simpler conceptually but less efficient

Hierholzer's algorithm:

Time: $O(m)$ (optimal)
More complex but builds cycles systematically
Preferred for implementation

Remark

Directed graphs: Hierholzer's algorithm extends naturally. A directed graph has an Eulerian circuit if and only if it's strongly connected and every vertex has in-degree equal to out-degree. The algorithm follows directed edges, maintaining the same cycle-merging structure.

Applications: De Bruijn graph construction for DNA assembly uses Hierholzer's algorithm to find Eulerian paths through sequences, enabling genome reconstruction from short reads.

ProofOptimality of Hierholzer

Any Eulerian circuit algorithm must examine each edge at least once to include it in the circuit. Hierholzer achieves $O(m)$ by visiting each edge at most twice (once to traverse, once during the merge phase). This is optimal for explicit circuit construction.

For just deciding Eulerian circuit existence, $O(m)$ is also optimal since we must verify degree parity, requiring edge examination.

■

The elegance of Hierholzer's algorithm lies in its recursive structure: build local cycles and merge them globally. This divide-and-conquer approach efficiently solves a problem that appears inherently global, demonstrating the power of local-to-global reasoning in graph algorithms.