The Seven Bridges of Königsberg asked: can you walk a route that crosses every bridge exactly once? Euler’s answer founded graph theory. Such a route — an Eulerian path — exists only when the graph is connected and has 0 or 2 vertices of odd degree. When it does, Hierholzer’s algorithm finds it in O(E): follow unused edges until you get stuck in a loop, then splice in more loops from any vertex that still has unused edges. Trace it edge by edge and watch the trail assemble.
O(E) time · exists iff connected & 0 or 2 odd-degree vertices · every edge used once
Eulerian path
A trail that uses every edge of the graph exactly once (vertices may repeat).
degree
How many edges touch a vertex. Odd-degree vertices decide whether a path can exist.
Walk until stuck (a closed loop), then splice loops from vertices with edges left.
euler.js — walk, get stuck, splice loops
Ready
Every vertex here has even degree, so an Eulerian circuit exists. Hierholzer walks unused edges until stuck, then backtracks — splicing any leftover loops in. Step to trace it.
0
at vertex
0/6
edges used
0
odd-degree
trail:
How it works
The degree rule falls right out of the definition. Every time an Eulerian trail passes through a vertex, it uses one edge to arrive and one to leave — consuming edges two at a time, so an interior vertex needs an even degree. The only vertices allowed an odd degree are the two endpoints of the trail (where you start with a leave and end with an arrival). Hence: a connected graph has an Eulerian circuit when every vertex is even, an Eulerian path when exactly two are odd (the endpoints), and neither otherwise.
1
Check the degree rule
Count odd-degree vertices. Zero → an Eulerian circuit exists; exactly two → an Eulerian path between them; anything else → no Eulerian trail at all.
2
Walk until stuck
From the start, keep following any unused edge. Because degrees are even, you can only get stuck back where you started — having traced a closed loop, though maybe not all edges yet.
3
Splice in leftover loops
If some vertex on your loop still has unused edges, start a new walk from there, trace another loop, and splice it into the trail at that vertex. Repeat until no edges remain.
✓
The stack method
Hierholzer implements this with a stack: push along unused edges; when a vertex has none left, pop it into the circuit. The reversed pop-order is the Eulerian trail, built in O(E).
Time
O(E)
Exists iff
0 or 2 odd
Each edge
used once
Founded
graph theory
The code
# Hierholzer — Eulerian circuit/path in O(E)def hierholzer(adj, start): # adj[v] = list of (neighbor, edge_id)
used, stack, circuit = set(), [start], []
while stack:
v = stack[-1]
edge = next(((u, i) for u, i in adj[v] if i notin used), None)
if edge:
u, i = edge
used.add(i); stack.append(u) # walk an unused edgeelse:
circuit.append(stack.pop()) # stuck: retreat, recordreturn circuit[::-1] # reversed = the trail
Quick check
1. When does a connected graph have an Eulerian path (but not a circuit)?
Zero odd-degree vertices gives an Eulerian circuit; exactly two gives an Eulerian path with those two as endpoints. Any other number of odd-degree vertices means no Eulerian trail exists.
2. Why must interior vertices of an Eulerian trail have even degree?
Every time the trail passes through a vertex it enters on one edge and leaves on another, using edges two at a time. Only the two endpoints can have an unmatched (odd) edge, so all other vertices must be even.
3. In Hierholzer’s stack method, when is a vertex added to the circuit?
You push along unused edges; when the top vertex has no unused edges remaining, you pop it and append it to the circuit. Reversing the final pop-order yields the Eulerian trail.
FAQ
What is an Eulerian path?
A trail through a graph that uses every edge exactly once (vertices may repeat). If it starts and ends at the same vertex it is an Eulerian circuit. Named after Euler, whose 1736 Seven Bridges of Königsberg solution founded graph theory.
When does an Eulerian path exist?
For a connected graph: an Eulerian circuit exists iff every vertex has even degree; an Eulerian path (non-circuit) exists iff exactly two vertices have odd degree, which become its endpoints. Any other number of odd-degree vertices → none.
How does Hierholzer’s algorithm work?
It builds the trail in O(E). Walk unused edges until stuck in a closed loop; if a vertex on the trail still has unused edges, walk another loop from it and splice it in; repeat until no edges remain. The stack version pushes along edges and pops edge-exhausted vertices into the circuit.
How is an Eulerian path different from a Hamiltonian path?
An Eulerian path visits every edge once; a Hamiltonian path visits every vertex once. Their difficulty differs enormously: Eulerian existence is an easy degree check and construction is O(E), while Hamiltonian-path existence is NP-complete.