Graph AlgosAlgorithmaka Euler trail, Hierholzer's algorithm, traverse every edge once

Eulerian Path

A walk that uses every edge exactly once; exists under simple degree conditions and is built greedily by Hierholzer's algorithm in O(E).

▶ VisualizePattern: Depth-First SearchPractice (1)
Progress

Overview

An Eulerian path (Euler trail) visits every edge of a graph exactly once; vertices may repeat. An Eulerian Circuit is the special case that starts and ends at the same vertex. This is the Königsberg-bridges problem, and unlike its vertex cousin (Hamiltonian path, NP-hard) it has a clean characterisation and a linear-time constructive algorithm.

Existence, undirected graph: all edges lie in one connected component, and the number of odd-degree vertices is 0 (circuit — start anywhere) or 2 (path — start at one odd vertex, end at the other).

Existence, directed graph: all edges in one weakly connected component, and either every vertex has out == in (circuit), or exactly one vertex has out − in = 1 (the start), exactly one has in − out = 1 (the end), and all others are balanced (path).

Construction is Depth-First Search (DFS)-like: Hierholzer's algorithm. Walk from the start, consuming edges greedily until stuck; when a vertex has no unused edges left, append it to the answer and back up. The answer, reversed, is the Eulerian path. It runs in O(V + E) using an "edge pointer" per vertex so every edge is looked at once.

EulerHierholzerdegree conditionsedges exactly oncedirectedundirectedO(V + E)

Intuition

A mental model before the formal terms.

Each time the walk passes *through* a vertex it uses two of that vertex's edges: one in, one out. So a vertex you neither start nor end at must have even degree, and the start / end (if different) must be the only odd ones. That is the whole degree condition; connectivity just ensures all edges are reachable.

Hierholzer: walk greedily and never worry about getting stuck, because you can only get stuck at the *end* vertex (every other vertex still has an exit whenever you enter it — even degree). When stuck, the vertex is done: freeze it onto the output and step back along your trail. If the vertex you stepped back to still has unused edges, take a detour from it; the detour will return to this same vertex and gets spliced in automatically because everything frozen after it comes later in the reversed output.

Example (directed): edges 0→1, 1→2, 2→0, 0→3. out−in: vertex 0 has +1 (start), 3 has −1 (end), others 0. Walk 0→1→2→0→3, stuck at 3: output [3]. Back to 0: no edges left → [3, 0]; back to 2, 1, 0 → [3, 0, 2, 1, 0]. Reverse: 0, 1, 2, 0, 3.

How it works

  1. Count degrees. Undirected: deg[v]. Directed: out[v], in[v].
  2. Check the existence condition. Pick the start: the odd-degree vertex (undirected) / the vertex with out − in = 1 (directed); if none, any vertex with at least one edge.
  3. Keep ptr[v] = index of the next unused edge in adj[v] (for undirected graphs also a used[edgeId] array, since each edge appears in two lists).
  4. Iterative Hierholzer: stack = [start]. While the stack is non-empty: let u = top; if ptr[u] < len(adj[u]), take the edge u → v (advance ptr[u]; skip used undirected edges), push v. Otherwise pop u and append it to path.
  5. Reverse path. If len(path) != E + 1, the edges were not all in one component — no Eulerian path exists.
  6. For the lexicographically smallest path (Reconstruct Itinerary), sort each adjacency list first; Hierholzer with greedy smallest-first choice then produces it.

Why it works

Necessity of the degree condition: a walk enters and leaves each interior visit through distinct edges, contributing +1 to both in- and out-degree (or +2 to undirected degree). Only the start and end can be unbalanced, by exactly one.

Sufficiency and Hierholzer's correctness: starting at start, the greedy walk can only get stuck at end (or start for a circuit), because every other vertex has as many exits as entries. When the walk is stuck at end, all vertices on the trail with leftover edges still satisfy the balanced condition on the *remaining* edges, so a fresh greedy walk from such a vertex returns to it — a closed sub-tour that the stack discipline splices in at the right position. Connectivity guarantees every edge is eventually reached from some trail vertex.

Each edge is consumed once (ptr never moves backwards), each vertex pushed once per incident edge, so O(V + E).

Recognition

How to tell a problem wants this.

  • "Use every road / flight / ticket / domino exactly once", "draw the figure without lifting the pen", "visit all edges".
  • A route-reconstruction problem where the input is a multiset of edges and the output is a single ordered walk (Reconstruct Itinerary).
  • De Bruijn sequences, "valid arrangement of pairs" — edges are the things to be arranged, vertices are the shared endpoints.
“connected groups” → Depth-First Search

Interactive visualization

Play, step, change the input. ← → and space work too.

A2B2C4D2E3F1
Stack (top → bottom)
empty
Path (built backwards)
empty
1/18Degrees: A=2, B=2, C=4, D=2, E=3, F=1. Odd-degree vertices: E, F. An Euler path needs 0 or 2 of them — every pass through a vertex uses two edges.
Top of stackOn the stackPopped into the pathEdge just traversedUsed edgeFinal Euler path
PseudocodeLearn Eulerian Path →
1odd = vertices with odd degree; if len(odd) not in {0, 2}: no Euler path
2start = odd[0] if odd else any vertex with an edge
3stack = [start]; path = []
4while stack not empty:
5  u = stack.top()
6  if u has an unused edge (u, v): mark it used; stack.push(v)
7  else: path.append(stack.pop())   # dead end: u is finished
8return reversed(path)
Variables
odd2
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V + E)
Speed

Pseudocode

1compute in/out (or deg); verify existence; pick start
2ptr[v] = 0 for all v; stack = [start]; path = []
3while stack not empty:
4  u = stack.top
5  if ptr[u] < len(adj[u]):
6    v = adj[u][ptr[u]]; ptr[u] += 1
7    stack.push(v)
8  else:
9    path.append(stack.pop())
10reverse(path)
11return path if len(path) == E + 1 else none

Implementations

1from typing import Optional
2 
3# An Eulerian path uses every EDGE exactly once (vertices may repeat).
4# Undirected: exists iff all edges lie in one component and the number of
5# odd-degree vertices is 0 or 2; start at an odd vertex when there are two.
6# Hierholzer's algorithm builds it in O(V + E).
7 
8 
91 · Feasibility first: count odd-degree vertices and pick a start
10def eulerian_start(adj: list[list[tuple[int, int]]]) -> int:
11    odd = 0
12    start = -1
13    any_with_edge = -1
14    for v, row in enumerate(adj):
15        if row and any_with_edge == -1:
16            any_with_edge = v
17        if len(row) % 2 == 1:
18            odd += 1
19            if start == -1:
20                start = v
21    if odd not in (0, 2):
22        return -1  # no Eulerian path at all
23    return start if start != -1 else any_with_edge  # odd vertex, else anywhere
24 
25 
262 · Hierholzer: walk until stuck, then splice in detours from the stack
27def eulerian_path(adj: list[list[tuple[int, int]]], edge_count: int) -> Optional[list[int]]:
28    start = eulerian_start(adj)
29    if start == -1:
30        return None
31    if edge_count == 0:
32        return [start]
33 
34    used = [False] * edge_count  # one flag per undirected edge id
35    it = [0] * len(adj)  # per-vertex neighbour cursor
36    stack = [start]
37    circuit: list[int] = []
38 
39    while stack:
40        u = stack[-1]
41        row = adj[u]
423 · Advance the cursor past edges already consumed (never rescan)
43        while it[u] < len(row) and used[row[it[u]][1]]:
44            it[u] += 1
45        if it[u] == len(row):
464 · Stuck: this vertex is finished, so it belongs at the end
47            circuit.append(u)
48            stack.pop()
49        else:
50            v, edge_id = row[it[u]]
51            used[edge_id] = True
52            stack.append(v)
53 
545 · The circuit is built backwards; a short one means disconnected edges
55    if len(circuit) != edge_count + 1:
56        return None
57    return circuit[::-1]
Walkthrough
  1. if odd not in (0, 2) reads as the mathematical condition directly.
  2. row = adj[u] is hoisted so the cursor loop does not re-index the adjacency list on every check.
  3. it[u] is the per-vertex cursor; naming it it rather than iter avoids shadowing the builtin.
  4. circuit[::-1] reverses into a new list, matching the list[int] return type — circuit.reverse() would return None.
  5. Optional[list[int]] makes the infeasible case explicit rather than overloading the empty list.
Complexity (this implementation)
time O(V + E) · space O(V + E)
Language notes
  • Naming a local iter shadows the builtin iter(), which is harmless here but a habit worth avoiding — hence it.
  • networkx.eulerian_path and networkx.is_eulerian implement this directly, including the directed variant.
  • x not in (0, 2) is a tuple membership test compiled to a constant tuple, and is both idiomatic and fast.
  • circuit[::-1] allocates a copy; circuit.reverse() is in place but returns None, which is a classic accidental-None bug.
Common mistakes in this language
  • Writing return circuit.reverse(), which returns None.
  • Shadowing iter (or list, set, id) with a local and confusing a later reader.
  • Using a set of frozensets for used edges, which cannot distinguish parallel edges.
Language differences that matter here
  • Signalling infeasibility: TypeScript and Python express it in the type (| null, Optional), while C++ and JavaScript return an empty container that collides with the trivial single-vertex case.
  • Reversal is in place and chainable in C++ (std::reverse) and JS/TS (Array.prototype.reverse), but Python list.reverse() returns None, so the slice [::-1] is the expression form.
  • Flag arrays: C++ prefers std::vector<char> over the vector<bool> proxy, JS/TS can opt into Uint8Array, and Python list[bool] stores pointers to the two bool singletons.
  • Only Python ships networkx.eulerian_path; C++ and JS/TS have nothing comparable in their ecosystems' defaults.

Complexity

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V + E)

Lexicographically smallest path needs sorted adjacency lists: O(E log E).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Every edge must be used exactly once: itinerary reconstruction, drawing puzzles, route inspection on balanced graphs.
  • Sequencing problems where items are edges between shared endpoints (dominoes, DNA fragments, De Bruijn sequences).
  • Any time the degree conditions hold — the algorithm is cheap and deterministic.
Avoid it when
  • Every vertex exactly once (Hamiltonian path / TSP) — NP-hard; use Bitmask DP for small n.
  • Degree conditions fail and you must still cover all edges with minimum repetition — that is the Chinese Postman problem (matching on odd vertices).
  • Shortest walk between two vertices — that is a shortest-path problem, not an Eulerian one.

Alternatives

Eulerian CircuitDepth-First Search (DFS)Bitmask DP

Common mistakes

  • Recursive Hierholzer that removes edges with list.remove or pop(0) — O(E) per step, O(E^2) total. Use the ptr[v] index (and pop() from the back of a sorted-descending list for lexicographic order).
  • Forgetting to reverse the output; the post-order builds the path back to front.
  • Undirected graphs: not marking edge ids as used, so an edge is traversed twice (once from each endpoint).
  • Checking degrees but not connectivity — a balanced graph with edges in two components has no Eulerian path; the len(path) == E + 1 check catches this.
  • Starting at the wrong vertex for a path (must start at the out − in = +1 vertex), which leaves edges unreachable.

Interview patterns

  • Reconstruct Itinerary: sort destinations, Hierholzer from "JFK", reverse the post-order.
  • Valid Arrangement of Pairs: each pair is a directed edge; find the start by degree difference; output the edges of the Eulerian path.
  • Explain degree conditions for directed vs undirected and why they are sufficient given connectivity.
Interview questions on this
Mock interviews

Example problems

Reconstruct Itineraryhard