Euler Paths and Hierholzer's Algorithm

What an Euler path actually is

Fix your attention on the edges, not the vertices. An Euler path (or Eulerian trail) is a walk through a graph that uses every edge exactly once. You are allowed to pass through the same vertex many times — that is expected — but you may never reuse an edge. If the walk finishes back at the vertex where it began, it is an Euler circuit (Eulerian cycle). The classic phrasing is: can you draw the figure in one continuous pen stroke, without lifting the pen and without retracing any line?

The remarkable thing Euler discovered is that whether such a walk exists is decided entirely by local parity — the degree of each vertex — and by whether the edges hang together in one piece. You never have to search. A single pass counting odd-degree vertices answers the existence question in O(V + E). This is what makes the topic a jewel of graph theory: a global structural property collapses to a trivial local count.

The degree conditions

Consider any vertex v that is not the start or end of the walk. Every time the walk enters v along one edge, it must leave along another. Entrances and exits pair up, so the edges incident to v that the walk uses come in twos — v must have even degree. The only vertices exempt from this pairing are the endpoints of the walk, which can have one unpaired edge each.

That single observation gives the full classification for a connected undirected graph (ignoring isolated vertices, which have no edges to walk):

• Euler circuit exists ⇔ every vertex has even degree. There are zero odd-degree vertices; you may start anywhere and you will return.
• Euler path (open, not a circuit) exists ⇔ exactly two vertices have odd degree. The walk must start at one odd vertex and end at the other.
• Neither exists if there are any other number of odd vertices. In fact the count of odd-degree vertices is always even (the handshaking lemma: ∑ deg = 2E), so the impossible cases are 4, 6, 8, … odd vertices.

The handshaking lemma — the sum of all degrees equals twice the number of edges, hence is even — is why you can never have an odd number of odd-degree vertices. Konigsberg's four odd vertices is a perfectly legal parity; the problem is that four is more than two.

The Seven Bridges of Konigsberg

In the Prussian city of Konigsberg (now Kaliningrad), the river Pregel split the town into four landmasses joined by seven bridges. The townsfolk amused themselves with a puzzle: could you take a walk that crosses each of the seven bridges exactly once? In 1736 Leonhard Euler proved that you cannot, and in doing so he stripped away every irrelevant detail — the shapes of the islands, the lengths of the bridges — and reduced the map to what we now call a graph: four vertices, seven edges.

The four landmasses have degrees 5, 3, 3, and 3 — all odd. An Euler walk tolerates at most two odd vertices, so a walk touching all seven bridges is impossible. The genius was not the arithmetic but the abstraction: Euler recognized that only the connection pattern mattered. This 1736 paper is universally cited as the origin of graph theory and, arguably, of topology. If the townsfolk had added an eighth bridge between two of the odd landmasses, two of them would become even, leaving exactly two odd vertices — and the walk would suddenly become possible.

How Hierholzer's algorithm works

Knowing a walk exists is one thing; producing it efficiently is another. Carl Hierholzer devised the constructive algorithm around 1871 but died before writing it up; his proof was reconstructed from memory by Christian Wiener (with Jacob Lüroth) and published posthumously in 1873. It is beautifully direct. The idea: a connected graph in which every vertex has even degree can be decomposed into edge-disjoint cycles, and those cycles can be stitched together into one grand tour.

The procedure, for an Euler circuit:

• Start anywhere and greedily follow unused edges, never repeating one, until you come back to your starting vertex. Because every vertex has even degree, you can never get stuck anywhere except back at the start — every entry has a matching unused exit. This gives a first closed cycle.
• Find a vertex on the current tour that still has unused edges. Starting there, trace a second closed cycle through the remaining edges. Splice this side-cycle into the main tour at that vertex.
• Repeat until no unused edges remain. The spliced-together cycles form the Euler circuit.

For an open Euler path (two odd vertices), simply begin the walk at one of the odd-degree vertices; the same splicing logic produces a trail ending at the other odd vertex. (A common trick is to temporarily add a virtual edge between the two odd vertices, find a circuit, then delete that edge — reopening the circuit into a path.)

The elegant iterative implementation uses an explicit stack. You push vertices as you walk forward; when you hit a vertex with no unused edges (a forced dead end), you pop it into the output list. Popping a stuck vertex, then continuing to walk from whatever is now on top, is exactly the "splice a side-cycle" operation done implicitly. Because vertices are emitted when they run out of edges, the output comes out reversed and is flipped at the end.

Why it is O(V + E)

Each edge is examined and consumed exactly once, and each vertex is pushed and popped a bounded number of times, so the total work is linear: O(V + E) time and O(E) space for the stack and output. The one implementation detail that matters is never re-scanning consumed edges. Keep a per-vertex pointer (an iterator or an index) into that vertex's adjacency list, and advance it past edges already used. If instead you linearly search a vertex's list for an unused edge each time you arrive, you can blow the bound up toward O(V·E). With the pointer trick, the amortized cost of finding the next edge at any vertex is O(1).

Euler vs Hamiltonian: an instructive contrast

Euler paths visit every edge once; Hamiltonian paths visit every vertex once. The two problems look like mirror images, but they sit on opposite sides of the great tractability divide of computer science.

	Euler path / circuit	Hamiltonian path / cycle
Visits each…	edge exactly once	vertex exactly once
Existence test	Count odd-degree vertices — O(V + E)	NP-complete (no known polynomial test)
Finding one	Hierholzer, O(V + E)	Exponential in the worst case
Clean characterization?	Yes — the degree/parity theorem	No simple necessary-and-sufficient condition
Related famous problem	Chinese Postman (route inspection)	Traveling Salesman Problem
Prize status	Solved 1736 / 1873	P vs NP — open millennium problem

That one word — edge versus vertex — is the difference between a two-line degree check and one of the hardest problems in computation. It is the cleanest illustration in all of graph theory that superficially similar questions can have radically different difficulty.

The directed version

For a directed graph, replace "even degree" with "balanced in-degree and out-degree":

• Eulerian circuit ⇔ the graph is connected (on vertices that have edges) and in-degree(v) == out-degree(v) for every vertex.
• Eulerian path (open) ⇔ exactly one vertex has out - in = +1 (the start), exactly one has in - out = +1 (the end), and all others are balanced.

"Connected" here means the vertices with edges form a single strongly-relevant component — concretely, that the underlying undirected graph restricted to nonzero-degree vertices is connected, plus the balance condition, which together force strong connectivity of that part. The directed case powers a genuinely important application: de Bruijn sequences and short-read genome assembly. Build a graph whose edges are the k-mers (length-k substrings) of a DNA read set; a reconstruction of the original sequence corresponds to an Eulerian path through that de Bruijn graph. This is exactly why Eulerian-path assembly (Pevzner et al.) is central to modern sequencing — the Hamiltonian formulation of the same task is intractable.

Implementation (Python)

An iterative Hierholzer for a directed graph. The same structure adapts to undirected graphs, but there you must give each edge a shared id stored in both adjacency lists and mark that id used on traversal, so the edge is never walked back the other way.

def hierholzer_directed(graph, start):
    """graph: dict[node] -> list[node] (directed adjacency list).
    Returns an Eulerian path/circuit as a list of vertices, or None
    if the degree/connectivity conditions do not hold."""
    # Per-vertex pointer into the adjacency list so consumed edges
    # are never re-scanned — this is what makes it O(V + E).
    ptr = {u: 0 for u in graph}
    stack = [start]
    circuit = []

    while stack:
        u = stack[-1]
        if ptr.get(u, 0) < len(graph.get(u, [])):
            v = graph[u][ptr[u]]   # next unused out-edge
            ptr[u] += 1            # consume it
            stack.append(v)        # walk forward
        else:
            circuit.append(stack.pop())  # dead end -> emit

    circuit.reverse()              # emitted in reverse order
    # A valid Euler tour uses every edge, so its length is E + 1.
    total_edges = sum(len(vs) for vs in graph.values())
    return circuit if len(circuit) == total_edges + 1 else None

Choosing start correctly matters: for a directed Eulerian path begin at the unique vertex with out - in = +1; for a circuit any vertex with an outgoing edge works. The final length check doubles as validation — if the graph fails the balance or connectivity conditions, the returned walk will be shorter than E + 1 and the function returns None.

Choosing the start and validating existence

def eulerian_start_directed(graph):
    """Return a valid start vertex, or None if no Eulerian path exists
    (by the degree balance test alone; still verify connectivity)."""
    outdeg, indeg = {}, {}
    for u, nbrs in graph.items():
        outdeg[u] = outdeg.get(u, 0) + len(nbrs)
        for v in nbrs:
            indeg[v] = indeg.get(v, 0) + 1

    start, plus_one, minus_one = None, 0, 0
    for v in set(outdeg) | set(indeg):
        d = outdeg.get(v, 0) - indeg.get(v, 0)
        if d == 1:
            plus_one += 1
            start = v            # the +1 vertex is the path's start
        elif d == -1:
            minus_one += 1
        elif d != 0:
            return None          # imbalance > 1 -> impossible

    if plus_one == 0 and minus_one == 0:
        # Perfectly balanced -> Eulerian circuit; start anywhere with an edge.
        return next((u for u in graph if graph[u]), None)
    if plus_one == 1 and minus_one == 1:
        return start             # open Eulerian path
    return None

Common misconceptions and pitfalls

• Confusing "vertex once" with "edge once." Euler is edges; Hamiltonian is vertices. An Euler path happily revisits vertices — it is the edges that must be unique. Mixing these up is the single most common error.
• Forgetting the connectivity requirement. The degree parities can all be perfect while the edges live in two separate components — then no single walk covers everything. Always check that all edges lie in one connected component (isolated, edge-free vertices are fine to ignore).
• Starting an open Euler path at the wrong vertex. When exactly two vertices are odd, you must start at one of them. Start anywhere else and you will strand yourself with an unused edge.
• Re-scanning consumed edges. Without a per-vertex pointer/iterator, repeatedly searching for an unused edge turns the O(V + E) algorithm into something quadratic on dense multigraphs.
• Undirected edge bookkeeping. In an undirected graph, each edge appears in two adjacency lists. When you traverse it, you must mark both copies used, or Hierholzer will happily walk the same edge twice from the other endpoint.
• Assuming the tour is unique. Except in trivial cases the Euler path is not unique — the order in which side-cycles are spliced changes the output. Any output that uses every edge once is correct.

Where Euler paths show up

• Genome assembly. De Bruijn graphs of k-mers turn sequence reconstruction into finding an Eulerian path — polynomial, unlike the older Hamiltonian formulation.
• Route inspection / Chinese Postman. Covering every street (edge) with minimum repetition; when the graph is already Eulerian the answer is a single Euler circuit with no repeats.
• DNA / RNA fragment ordering and de Bruijn sequences. The shortest cyclic string containing every length-k word once is an Eulerian circuit in a de Bruijn graph.
• Drawing and CNC/pen-plotter path planning. Minimizing pen lifts on a figure is precisely asking for an Euler (or near-Euler) traversal.
• Circuit board and network diagnostics. Traversing every connection exactly once for testing coverage.