Graph AlgosAlgorithmaka Euler tour, Euler cycle, closed Eulerian trail

Eulerian Circuit

A closed walk using every edge exactly once; exists iff the graph is connected on its edges and every vertex is balanced.

▶ VisualizePattern: Depth-First SearchPractice (1)
Progress

Overview

An Eulerian circuit is an Eulerian Path that starts and ends at the same vertex. It exists in an undirected graph iff every vertex has even degree and all edges lie in one connected component; in a directed graph iff every vertex has in-degree == out-degree and all edges lie in one weakly connected component. Isolated vertices are allowed — they have degree 0.

The construction is Hierholzer's algorithm exactly as for the path case, except that the start vertex is arbitrary (any vertex with at least one edge) and the output is a cycle: first and last vertices coincide. Because there is no distinguished start, the circuit can be rotated to begin at any vertex on it.

Classic uses: the Chinese Postman problem (after pairing odd vertices), De Bruijn sequences, and checking whether a figure can be drawn in one closed stroke.

EulerHierholzercircuiteven degreebalancedO(V + E)

Intuition

A mental model before the formal terms.

A closed tour enters and leaves every vertex the same number of times, including the start (it leaves at the beginning and returns at the end). So every vertex's edges pair off into in/out couples — even degree, or in == out. The Königsberg bridges failed this: all four land masses had odd degree.

Hierholzer on a balanced graph: wherever you wander you can never get stuck except back at the start, since every other vertex has an exit for every entry. Each time you close a loop, look back along it for a vertex with unused edges and grow a side loop from there; the stack-based implementation does this splicing for free.

Example (undirected): square 0—1—2—3—0 plus diagonal-free — all degrees 2. Circuit: 0, 1, 2, 3, 0. Add edges 1—3 and 1—3 (a double edge): degrees become [2, 4, 2, 4], still even; circuit 0, 1, 3, 1, 2, 3, 0.

How it works

  1. Compute degrees. Undirected: reject if any deg[v] is odd. Directed: reject if any in[v] != out[v].
  2. Pick start = any vertex with an incident edge (if the graph has no edges, the empty circuit is trivially fine).
  3. Run iterative Hierholzer: stack = [start]; while non-empty, take the top u; if it has an unused edge u → v, mark it used and push v; otherwise pop u into path.
  4. Reverse path (for a circuit reversal is optional in undirected graphs but required in directed ones). Verify len(path) == E + 1; otherwise the edges are not all connected.

Why it works

Necessity: in a closed trail every visit to a vertex, including the start/end, consumes one entering and one leaving edge; summing gives even degree (undirected) or in == out (directed).

Sufficiency: with every vertex balanced, a greedy walk from start can only terminate at start (any other vertex has a free exit when entered). The stack discipline of Hierholzer then splices closed sub-tours from vertices with leftover edges; connectivity of the edge set ensures no edge is left out.

Every edge is consumed once; each vertex is pushed once per incident edge: O(V + E).

Recognition

How to tell a problem wants this.

  • "Return to the starting point after using every road / bridge exactly once".
  • "Can this figure be drawn in a single closed stroke?"
  • All degrees even (or in == out everywhere) is stated or easily verified.
“connected groups” → Depth-First Search

Interactive visualization

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

Showing the closely related Eulerian Path visualization.

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

1if any vertex unbalanced: return none
2start = 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 used; stack.push(v)
7  else: path.append(stack.pop())
8reverse(path)
9return path if len(path) == E + 1 else none

Implementations

1from typing import Optional
2 
3# An Eulerian CIRCUIT is an Eulerian path that returns to its start.
4# Undirected: exists iff every vertex has even degree and all edges lie in
5# one connected component. Directed: indegree == outdegree everywhere, and
6# the graph is connected when viewed as undirected.
7 
8 
91 · Undirected feasibility: every degree even, all edges in one component
10def has_eulerian_circuit(adj: list[list[tuple[int, int]]]) -> bool:
11    first = -1
12    for v, row in enumerate(adj):
13        if len(row) % 2 == 1:
14            return False  # an odd vertex forbids a circuit
15        if row and first == -1:
16            first = v
17    if first == -1:
18        return True  # no edges: trivially Eulerian
19 
202 · All edge-bearing vertices must be reachable from one of them
21    seen = [False] * len(adj)
22    seen[first] = True
23    stack = [first]
24    while stack:
25        u = stack.pop()
26        for v, _ in adj[u]:
27            if not seen[v]:
28                seen[v] = True
29                stack.append(v)
30    return all(not row or seen[v] for v, row in enumerate(adj))
31 
32 
333 · Hierholzer again, but the start may be any edge-bearing vertex
34def eulerian_circuit(adj: list[list[tuple[int, int]]], edge_count: int) -> Optional[list[int]]:
35    if not has_eulerian_circuit(adj):
36        return None
37    start = next((v for v, row in enumerate(adj) if row), 0)
38    if edge_count == 0:
39        return [start]
40 
41    used = [False] * edge_count
42    it = [0] * len(adj)
43    stack = [start]
44    circuit: list[int] = []
45 
464 · Walk until stuck; exhausted vertices are emitted in post-order
47    while stack:
48        u = stack[-1]
49        row = adj[u]
50        while it[u] < len(row) and used[row[it[u]][1]]:
51            it[u] += 1
52        if it[u] == len(row):
53            circuit.append(u)
54            stack.pop()
55        else:
56            v, edge_id = row[it[u]]
57            used[edge_id] = True
58            stack.append(v)
59 
605 · A circuit ends where it began: circuit[0] == circuit[-1]
61    return circuit[::-1]
Walkthrough
  1. all(not row or seen[v] for v, row in enumerate(adj)) states the connectivity condition as one short-circuiting generator expression.
  2. next((v for v, row in enumerate(adj) if row), 0) finds the first edge-bearing vertex with a default, replacing an explicit loop.
  3. for v, _ in adj[u] unpacks the pair and discards the edge id with the conventional underscore.
  4. if row uses list truthiness for "has edges", which is idiomatic Python.
  5. circuit[::-1] returns the reversed copy; circuit.reverse() would return None.
Complexity (this implementation)
time O(V + E) · space O(V + E)
Language notes
  • networkx.is_eulerian and networkx.eulerian_circuit implement both halves directly, including the directed case.
  • next(generator, default) is the standard "first match or fallback" idiom and avoids a StopIteration on an empty generator.
  • Truthiness on a list (if row) is idiomatic here, though if len(row) > 0 is clearer when the reader might expect a numeric check.
  • all() over a generator short-circuits, so a disconnected graph is rejected as soon as the first stranded vertex is seen.
Common mistakes in this language
  • Writing return circuit.reverse() and returning None.
  • Using next(...) without a default and raising StopIteration on an edgeless graph.
  • Applying the path parity condition and reporting an open walk as a circuit.
Language differences that matter here
  • Expressing "every edge-bearing vertex was reached": a C++ loop, a JavaScript loop, a TypeScript every with an index, and a Python all() over a generator — increasingly compact, all short-circuiting.
  • "First element matching a predicate, with a default" is a one-liner in Python (next(gen, 0)) and a loop everywhere else.
  • Reversal again splits Python from the rest: list.reverse() returns None, so the slice is the expression form, while C++ and JS/TS reverse in place.
  • Only Python has this in a library (networkx.eulerian_circuit), and only TypeScript can encode the infeasible case in the return type.

Complexity

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V + E)
Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Closed tours covering every edge once: inspection routes, one-stroke drawings, De Bruijn sequences.
  • As the second phase of the Chinese Postman problem after duplicating edges to make all degrees even.
Avoid it when
  • Exactly two odd-degree vertices — that is an open Eulerian Path, not a circuit.
  • Visiting every vertex once and returning (Hamiltonian cycle / TSP) — NP-hard; see Bitmask DP.
  • Graphs with unbalanced vertices where you may repeat edges — minimise repetitions via matching instead.

Alternatives

Eulerian PathDepth-First Search (DFS)

Common mistakes

  • Checking degrees but not that all edges are in one component.
  • Requiring *every* vertex to be reachable — isolated vertices (degree 0) are allowed.
  • In directed graphs, checking only that total in equals total out (always true) instead of per vertex.
  • Using an O(E) edge removal per step instead of the ptr/used bookkeeping.

Interview patterns

  • Decide "is there a closed walk covering all edges" from the degree parities in O(V + E).
  • Build a De Bruijn sequence: vertices are (k−1)-mers, edges are k-mers; an Eulerian circuit reads off the sequence.
Interview questions on this
Mock interviews

Example problems

Reconstruct Itineraryhard