Hierholzer's Algorithm

A Bit of History

Carl Hierholzer, a German mathematician, discovered this algorithm shortly before his own death in 1871 at the age of just 31. He never published it himself — the paper "Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren" ("On the possibility of traversing a line-figure without repetition and without interruption") was compiled from his notes by colleagues Christian Wiener and Jacob Lüroth and published posthumously in 1873. It gave the first constructive, efficient method for actually finding an Eulerian circuit — Euler's own 1736 work (from Part 12) had proven when one exists, but not efficiently how to find it.

Working Principle

Recall from Part 12: a connected graph has an Eulerian circuit if and only if every vertex has even degree. Hierholzer's algorithm constructs one directly:

1. Start at any vertex and greedily follow unused edges, marking each as used, until returning to the starting vertex (this is guaranteed to happen, since every vertex has even degree — arriving at a vertex always leaves an unused edge to leave by, except at the start). This produces a closed sub-circuit, not necessarily covering all edges yet.
2. While any vertex on the current circuit still has unused edges, splice in a new sub-circuit: start a fresh greedy walk from that vertex (again guaranteed to close back on itself by the same even-degree argument), and merge it into the main circuit at that point.
3. Repeat until every edge has been used exactly once. The result is a single Eulerian circuit covering every edge.

Worked Example

Consider a 4-vertex graph shaped like two triangles sharing a vertex \(C\): edges \(A\text{-}B\), \(B\text{-}C\), \(C\text{-}A\) (first triangle) and \(C\text{-}D\), \(D\text{-}E\), \(E\text{-}C\) (second triangle). Every vertex has even degree (\(A,B,D,E\) have degree 2; \(C\) has degree 4). Starting a greedy walk at \(A\): \(A \to B \to C \to A\) closes the first triangle, but \(C\) still has 2 unused edges. Splicing a new walk from \(C\): \(C \to D \to E \to C\) closes the second triangle. Merging at \(C\) gives the full Eulerian circuit \(A \to B \to C \to D \to E \to C \to A\), using all 6 edges exactly once.

Correctness

The algorithm's correctness rests on a simple invariant: at every point, the "leftover" unused edges (removing whatever the current partial circuit has already used) still form a graph where every vertex has even degree — since the partial circuit itself uses an even number of edges at every internal vertex it passes through (it enters and exits each time). By induction on the number of remaining edges, this guarantees a fresh closed sub-circuit can always be found and spliced in wherever unused edges remain, until none are left.

Complexity Analysis

Using an adjacency-list representation with an efficient "remove used edge" mechanism (e.g., a pointer per vertex tracking the next unexplored edge, or a doubly-linked adjacency structure), each edge is visited and marked used exactly once across the entire algorithm:

$$\text{Time: } O(E) \qquad \text{Space: } O(V + E)$$

Linear time — matching the intuitive lower bound that any algorithm must at least look at every edge once.

Implementation

from collections import defaultdict

def hierholzer(edges, start):
    """
    edges: list of (u, v) undirected edges. Assumes graph is connected and
    every vertex has even degree (a valid Eulerian circuit exists).
    Returns the circuit as a list of vertices.
    """
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    circuit = []
    stack = [start]
    # Use per-vertex pointers so already-used edges are skipped in O(1) amortized
    ptr = defaultdict(int)

    while stack:
        v = stack[-1]
        if ptr[v] < len(adj[v]):
            u = adj[v][ptr[v]]
            ptr[v] += 1
            if u == -1:
                continue  # marked as used
            # Mark the reverse edge as used by finding and nulling it
            for i, x in enumerate(adj[u]):
                if x == v:
                    adj[u][i] = -1
                    break
            stack.append(u)
        else:
            circuit.append(stack.pop())

    return circuit[::-1]

edges = [('A','B'), ('B','C'), ('C','A'), ('C','D'), ('D','E'), ('E','C')]
print(hierholzer(edges, 'A'))  # e.g. ['A', 'B', 'C', 'D', 'E', 'C', 'A']

#include <vector>
#include <unordered_map>
#include <iostream>
using namespace std;

vector<int> hierholzer(unordered_map<int, vector<int>>& adj, int start) {
    unordered_map<int, int> ptr;
    vector<int> circuit, stack = {start};

    while (!stack.empty()) {
        int v = stack.back();
        auto& neighbors = adj[v];
        if (ptr[v] < (int)neighbors.size()) {
            int u = neighbors[ptr[v]++];
            if (u == -1) continue;
            // Mark the reverse edge as used
            for (int& x : adj[u]) {
                if (x == v) { x = -1; break; }
            }
            stack.push_back(u);
        } else {
            circuit.push_back(v);
            stack.pop_back();
        }
    }
    reverse(circuit.begin(), circuit.end());
    return circuit;
}

int main() {
    // Vertices encoded as ints: A=0, B=1, C=2, D=3, E=4
    unordered_map<int, vector<int>> adj;
    vector<pair<int,int>> edges = {{0,1},{1,2},{2,0},{2,3},{3,4},{4,2}};
    for (auto& e : edges) {
        adj[e.first].push_back(e.second);
        adj[e.second].push_back(e.first);
    }
    vector<int> circuit = hierholzer(adj, 0);
    for (int v : circuit) cout << v << " ";
    cout << endl;  // 0 1 2 3 4 2 0
    return 0;
}

import java.util.*;

class Hierholzer {
    static List<Integer> solve(Map<Integer, List<Integer>> adj, int start) {
        Map<Integer, Integer> ptr = new HashMap<>();
        List<Integer> circuit = new ArrayList<>();
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            int v = stack.peek();
            List<Integer> neighbors = adj.get(v);
            int p = ptr.getOrDefault(v, 0);
            if (p < neighbors.size()) {
                int u = neighbors.get(p);
                ptr.put(v, p + 1);
                if (u == -1) continue;
                List<Integer> uNeighbors = adj.get(u);
                for (int i = 0; i < uNeighbors.size(); i++) {
                    if (uNeighbors.get(i) == v) { uNeighbors.set(i, -1); break; }
                }
                stack.push(u);
            } else {
                circuit.add(stack.pop());
            }
        }
        Collections.reverse(circuit);
        return circuit;
    }

    public static void main(String[] args) {
        Map<Integer, List<Integer>> adj = new HashMap<>();
        int[][] edges = {{0,1},{1,2},{2,0},{2,3},{3,4},{4,2}};
        for (int i = 0; i < 5; i++) adj.put(i, new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        System.out.println(solve(adj, 0));  // [0, 1, 2, 3, 4, 2, 0]
    }
}

Real-World Applications

Exercises

1. Trace through the worked example by hand, explicitly noting at which vertex the second sub-circuit gets spliced into the first, and why that vertex was chosen.
2. Explain why the algorithm requires the graph to already be known to have every vertex at even degree — what would go wrong if you ran it on a graph violating this condition?
3. Modify the algorithm (in your own implementation) to find an Eulerian trail (not necessarily a closed circuit) on a graph with exactly two odd-degree vertices, by starting the walk at one of those two vertices.
4. Challenge: Apply Hierholzer's algorithm to the classic Seven Bridges of Königsberg graph from Part 12, and confirm it correctly reports no Eulerian circuit exists (since all four Königsberg landmasses have odd degree).

Limitations