Hierholzer's Algorithm

A Bit of History

Carl Hierholzer developed the method in the nineteenth century; it appeared posthumously in 1873. Euler's bridge problem had established the structural question—when can every edge be crossed exactly once?—while Hierholzer supplied the constructive idea that modern implementations still use: build closed walks and splice them into one another.

The distinction matters. An existence theorem tells us a route is possible; an algorithm must also represent parallel edges, consume each physical edge once, and produce the vertices in the right order. Hierholzer accomplishes all of that in time proportional to the graph itself.

When Does an Euler Route Exist?

An Euler trail uses every edge exactly once. An Euler circuit is an Euler trail that returns to its starting vertex. Vertices may repeat; edges may not. For an undirected graph, ignore isolated vertices when checking connectivity.

Working Principle

Assume first that an undirected Euler circuit exists. Hierholzer's conceptual version has three moves:

1. Walk greedily. Start at any non-isolated vertex and keep taking unused edges until the walk closes.
2. Find a splice point. If unused edges remain, connectivity guarantees that some vertex already on the circuit touches one of them.
3. Splice and repeat. Build another closed walk from that vertex and insert it into the current circuit. Stop when all edges are consumed.

Worked Example: Splicing Two Cycles

Consider two triangles that share vertex C. The six edge IDs are $e_0=AB$, $e_1=BC$, $e_2=CA$, $e_3=CD$, $e_4=DE$, and $e_5=EC$. Vertices A, B, D, and E have degree 2; C has degree 4.

There are $E=6$ edges, so a valid vertex sequence must contain $E+1=7$ entries. That simple count is a valuable postcondition, but edge IDs are still needed to verify that parallel edges were individually consumed.

The Stack View: Splicing Without List Surgery

Production code usually does not build separate cycles and physically insert one list into another. It keeps one stack. While the top vertex has an unused incident edge, traverse that edge and push the neighbor. When the top has no unused edge, pop it into the output. These pops finalize the route from the end backward, so the output is reversed once at the end.

Why It Is Correct

1. A greedy walk cannot get stuck at the wrong vertex

In an even-degree graph, every time the walk enters a vertex other than its start, it uses one incident edge to arrive. The remaining unused incident edges there have odd count, so at least one is available to leave. Therefore the first maximal walk can stop only at its starting vertex; it is a closed walk.

2. Unused edges attach to the current circuit

If edges remain and all non-isolated vertices belong to one connected component, some unused edge is reachable from the circuit. Along a connecting path, the first unused edge begins at a vertex already reached by used edges. That vertex is a valid splice point.

3. Splicing preserves the invariant

Insert a closed sub-circuit at a shared vertex. Both pieces remain continuous, no edge is duplicated, and the combined walk is still closed. Each iteration consumes at least one new edge, so the process terminates. At termination, every edge appears exactly once.

Complexity Analysis

Store an adjacency list, give every physical edge a unique ID, and mark that ID used the first time either endpoint selects it. Each adjacency entry is inspected at most once, each edge is consumed once, and each vertex occurrence is pushed and popped once:

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

If the input is already known to contain edges and only traversal work is counted, the central loop is often described as $O(E)$. The $O(V)$ term covers building/checking the representation and isolated vertices.

Implementation

The implementations below handle undirected multigraphs, including parallel edges and self-loops. They return a circuit when all degrees are even, an open trail when exactly two are odd, and failure otherwise. The final $E+1$ length check also catches disconnected edge-bearing components.

def euler_trail(n, edges):
    """Return a vertex list using every undirected edge once, or None."""
    if n < 0:
        return None

    adj = [[] for _ in range(n)]
    degree = [0] * n
    for edge_id, (u, v) in enumerate(edges):
        if not (0 <= u < n and 0 <= v < n):
            return None
        adj[u].append((v, edge_id))
        adj[v].append((u, edge_id))  # a self-loop intentionally appears twice
        degree[u] += 1
        degree[v] += 1

    if not edges:
        return [0] if n else []

    odd = [v for v in range(n) if degree[v] % 2]
    if len(odd) not in (0, 2):
        return None

    # For an open trail, an odd vertex must be the start.
    start = odd[0] if odd else next(v for v in range(n) if degree[v])
    used = [False] * len(edges)
    stack = [start]
    route_reversed = []

    while stack:
        v = stack[-1]
        while adj[v] and used[adj[v][-1][1]]:
            adj[v].pop()

        if not adj[v]:
            route_reversed.append(stack.pop())
        else:
            u, edge_id = adj[v].pop()
            used[edge_id] = True
            stack.append(u)

    if len(route_reversed) != len(edges) + 1:
        return None  # some edge-bearing component was unreachable

    return route_reversed[::-1]


edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 2)]
print(euler_trail(5, edges))  # one answer: [0, 2, 4, 3, 2, 1, 0]

#include <algorithm>
#include <iostream>
#include <optional>
#include <utility>
#include <vector>
using namespace std;

optional<vector<int>> eulerTrail(
    int n, const vector<pair<int, int>>& edges) {
    if (n < 0) return nullopt;

    vector<vector<pair<int, int>>> adj(n);
    vector<int> degree(n, 0);
    for (int id = 0; id < (int)edges.size(); ++id) {
        auto [u, v] = edges[id];
        if (u < 0 || u >= n || v < 0 || v >= n) return nullopt;
        adj[u].push_back({v, id});
        adj[v].push_back({u, id});
        ++degree[u]; ++degree[v];
    }

    if (edges.empty()) return n ? vector<int>{0} : vector<int>{};

    vector<int> odd;
    for (int v = 0; v < n; ++v)
        if (degree[v] % 2) odd.push_back(v);
    if (odd.size() != 0 && odd.size() != 2) return nullopt;

    int start = odd.empty()
        ? int(find_if(degree.begin(), degree.end(), [](int d) { return d; })
              - degree.begin())
        : odd[0];
    vector<bool> used(edges.size(), false);
    vector<int> stack{start}, reversedRoute;

    while (!stack.empty()) {
        int v = stack.back();
        while (!adj[v].empty() && used[adj[v].back().second])
            adj[v].pop_back();

        if (adj[v].empty()) {
            reversedRoute.push_back(v);
            stack.pop_back();
        } else {
            auto [u, id] = adj[v].back();
            adj[v].pop_back();
            used[id] = true;
            stack.push_back(u);
        }
    }

    if (reversedRoute.size() != edges.size() + 1) return nullopt;
    reverse(reversedRoute.begin(), reversedRoute.end());
    return reversedRoute;
}

int main() {
    vector<pair<int, int>> edges = {
        {0,1}, {1,2}, {2,0}, {2,3}, {3,4}, {4,2}
    };
    auto route = eulerTrail(5, edges);
    if (route) for (int v : *route) cout << v << ' ';
}

import java.util.*;

class Hierholzer {
    record Arc(int to, int id) {}

    static List<Integer> eulerTrail(int n, int[][] edges) {
        if (n < 0) return null;

        List<List<Arc>> adj = new ArrayList<>();
        for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
        int[] degree = new int[n];

        for (int id = 0; id < edges.length; id++) {
            int u = edges[id][0], v = edges[id][1];
            if (u < 0 || u >= n || v < 0 || v >= n) return null;
            adj.get(u).add(new Arc(v, id));
            adj.get(v).add(new Arc(u, id));
            degree[u]++; degree[v]++;
        }

        if (edges.length == 0)
            return n == 0 ? new ArrayList<>() : new ArrayList<>(List.of(0));

        List<Integer> odd = new ArrayList<>();
        for (int v = 0; v < n; v++) if (degree[v] % 2 == 1) odd.add(v);
        if (odd.size() != 0 && odd.size() != 2) return null;

        int start = odd.isEmpty() ? 0 : odd.get(0);
        while (degree[start] == 0) start++;

        boolean[] used = new boolean[edges.length];
        int[] next = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        List<Integer> reversedRoute = new ArrayList<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            int v = stack.peek();
            List<Arc> list = adj.get(v);
            while (next[v] < list.size() && used[list.get(next[v]).id()]) next[v]++;

            if (next[v] == list.size()) {
                reversedRoute.add(stack.pop());
            } else {
                Arc arc = list.get(next[v]++);
                used[arc.id()] = true;
                stack.push(arc.to());
            }
        }

        if (reversedRoute.size() != edges.length + 1) return null;
        Collections.reverse(reversedRoute);
        return reversedRoute;
    }

    public static void main(String[] args) {
        int[][] edges = {{0,1}, {1,2}, {2,0}, {2,3}, {3,4}, {4,2}};
        System.out.println(eulerTrail(5, edges));
    }
}

Why Edge IDs Matter

In a multigraph, two edges can have the same endpoints. Marking “the edge from $u$ to $v$” by endpoint value is ambiguous. A unique ID represents the physical edge; both undirected adjacency entries store that same ID. The technique also handles a self-loop correctly: its two adjacency entries share one ID, so the loop is consumed only once.

Directed Graphs

The traversal loop barely changes: store only outgoing arcs and consume each once. The existence conditions do change.

For an open directed trail, begin at the unique vertex with one extra outgoing edge. A useful reduction is to temporarily add an arc from the intended end back to the start: the augmented graph should satisfy the circuit conditions.

Where It Appears

Hierholzer vs. Fleury

Pitfalls & Debugging Checklist

A stronger test validates the output edge by edge: its consecutive pairs must consume the input edge multiset exactly once. Checking only the length can miss a buggy implementation that repeats one edge and omits another.

Exercises