The idea: use every edge exactly once
An Euler path is a walk through a graph that uses every edge exactly once. Vertices may be visited as often as you like. If the walk ends where it started, it is an Euler circuit. It is the old puzzle "draw this figure without lifting the pen and without going over a line twice". Leonhard Euler studied it in 1736 for the seven bridges of Königsberg, and that paper is usually called the start of graph theory.
The page does it in two steps. Step 1 counts degrees and decides whether an Euler path can exist at all. Step 2 finds one with Hierholzer's algorithm, which needs only one pass over the edges.
Step 1: why the degrees decide it
The degree of a vertex is the number of edge ends that touch it. Each time a walk passes through a vertex, it comes in on one edge and leaves on another, so it uses up two edge ends. A vertex in the middle of the walk therefore needs an even degree. Only the first and the last vertex can have one edge end left over.
| Odd-degree vertices | Result (graph connected) | Where to start |
|---|---|---|
| 0 | Euler circuit ✓ | anywhere; you end where you started |
| 2 | Euler path ✓, no circuit | at one odd vertex; you end at the other |
| 4, 6, … | none ✗ | – |
The number of odd vertices is always even, because the degrees add up to twice the number of edges. So "exactly 1 odd vertex" can't happen. The edges must also lie in one connected piece (vertices with no edges don't matter). Demo 5 has only even degrees, but two separate triangles, so there is no circuit. In Königsberg (Demo 2) all four land masses have an odd number of bridges, so no walk crosses every bridge once.
Euler proved that the condition is necessary. Carl Hierholzer proved in 1873 that it is also sufficient, by giving the construction below.
Step 2: Hierholzer's algorithm
Start at the right vertex and walk along unused edges, marking each one used, until you get stuck. With even degrees you can only get stuck back at the start: every other vertex you enter still has an unused edge to leave by. The result is a closed loop, but it may have left edges unused. Those are picked up by detours that start from a vertex on the loop and are spliced into it.
With an explicit stack, the whole thing is a few lines:
stack = [start]; circuit = []
while stack is not empty:
u = top of stack
if u has an unused edge u–v:
mark u–v used
push v // keep walking
else:
pop u
put u at the front of circuit // u is finished
return circuit // E + 1 vertices
In the animation, the stack row holds the current walk. Edges are grey while unused, orange once walked (they are still on the stack), and turn the colour of their walk once their end vertex is popped into the circuit. The circuit row has exactly E + 1 slots and fills from the right, because each popped vertex goes to the front. Demo 1 (the house) needs no detour: one walk from the odd corner A uses all 8 edges and ends at the other odd corner B.
Splicing a detour
In the bowtie (Demo 3), the walk A → B → C → A closes after three edges, stuck at A while B's other triangle is unused. The algorithm pops A, then C. Now B is on top, and B still has an unused edge. So a new walk starts at B: B → D → E → B. When it is stuck too, everything is popped. The second walk's vertices land in the circuit right next to the B where it started, so it ends up inside the first loop.
No list surgery is needed: the stack does the splice for free. Popping walks back along the first loop until it reaches a vertex with unused edges, and the detour is pushed on top of exactly that vertex. Demo 4 (three triangles) needs two detours: walk 2 from C, then walk 3 from B.
Why it works
- An edge is marked used only when it is walked, and it is never walked twice, so no edge appears twice.
- A vertex is popped only when it has no unused edges. By the time the stack is empty, every vertex reached has none left, and since the graph is connected, that covers every edge. So the circuit has all E edges and E + 1 vertices.
- Consecutive vertices in the circuit are always joined by the edge that was walked between them, so the result really is a walk.
Running time
Each edge is walked once and each stack entry is pushed and popped once. With a pointer into each adjacency list (so "the next unused edge of u" never rescans edges already used), Hierholzer's algorithm runs in O(V + E) time. The page simply takes the unused edge with the lowest number, which makes every run the same.
| Hierholzer | Fleury | |
|---|---|---|
| Idea | walk until stuck, splice detours | never cross a bridge unless you must |
| Extra work per edge | none | a bridge test (a graph search) |
| Time | O(V + E) | O(E²) or worse |
| Walk built | backwards, by the pops | forwards, edge by edge |
Directed graphs
For a directed graph the rule counts arrows instead of edge ends. An Euler circuit needs in-degree = out-degree at every vertex. An Euler path needs one vertex with one extra outgoing edge (the start) and one with one extra incoming edge (the end). Hierholzer's algorithm is the same, following only outgoing edges. The popped order is then the circuit backwards, which is why the pseudocode puts each vertex at the front.
Where Euler paths are used
- Genome assembly. Short DNA reads are cut into overlapping pieces that form a de Bruijn graph; the genome is read off an Euler path through it.
- De Bruijn sequences. An Euler circuit in the de Bruijn graph gives the shortest string that contains every k-digit code once (used for lock codes and in testing).
- Route inspection (the Chinese postman problem): a snow plough or a postman must cover every street. If odd vertices exist, the cheapest way is to repeat some streets so all degrees become even, then follow an Euler circuit.
- Drawing and cutting. Plotters, embroidery and CNC machines draw a figure as few pen strokes as possible.
Don't confuse it with a Hamiltonian path, which visits every vertex once: that problem is NP-complete, while the Euler question is answered by counting degrees. See also Depth-First Search, which walks a graph with a stack the same way, and Strongly Connected Components (Tarjan) for checking that a directed graph is connected enough.
See also Euler's formula V − E + F = 2: Euler's other graph theorem, about counting vertices, edges and faces of a drawing with no crossings.
What the page leaves out
Directed graphs and self-loops (the algorithm is the same, the drawing would need arrows); a pointer per adjacency list instead of scanning for the lowest unused edge; Fleury's algorithm, step by step; counting how many different Euler circuits a graph has (the BEST theorem); and the Chinese postman problem, which adds the cheapest set of repeated edges first.