Can you walk a graph using every edge exactly once and return to start? Euler answered when in 1736 — every vertex must have even degree — solving the Seven Bridges of Konigsberg and founding graph theory. But Euler gave no method; Hierholzer did, 137 years later: walk a loop, then splice in loops through the leftover edges.
THE TECHNIQUE walk a loop, splice in the rest
First the test: an Euler circuit exists iff the graph is connected and every vertex has even degree. Then Hierholzer builds one: walk unused edges until you return to start (a closed loop); if any vertex on it still has unused edges, walk a new loop from there and splice it in; repeat until no edge is left. Watch it trace and splice. live demo
HISTORY & CREDIT the theorem, then the method, 137 years apart
“Euler gave the algorithm” — he gave the algorithmcondition (and founded graph theory); the constructive method is Hierholzer’s. cited
1736 · Leonhard Euler proves the Seven Bridges of Konigsberg has no such walk (its four landmasses have odd degree) — the paper that founds graph theory and prefigures topology. He gives the criterion, not a construction. 1873 · Carl Hierholzer gives the algorithm — walk-and-splice, linear time — published posthumously (he died in 1871, aged 30). 1883 · Fleury gives the more famous but slower rule (“never cross a bridge you can’t come back over”) — O(E²) vs Hierholzer’s O(E). the reach · Euler circuits now route DNA fragment assembly, drone coverage, and mail-carrier tours.
One of mathematics’ cleanest “iff”s, and the birth certificate of a whole field. Euler 1736 / Hierholzer 1873
RECOMMEND FOR I-13 a degree scan and an edge-used flag array
The existence test is an integer parity scan; the construction rides an edge-used array and a stack — and the test runs on the compiler:
$ i13 run hier.i13 # a 5-vertex graph vs the Konigsberg bridges
graph: all degrees even -> ok = 1 Konigsberg: 3,3,3,5 odd -> ok = 0
Recommend: the existence test runs cleanly — a degree-count array, checked all-even (verified ok=1 for the graph, ok=0 for Konigsberg). The construction rides a boolean edge-used[] array plus a per-vertex next-edge index and an explicit stack — all bounded arrays. One mild wall: the connectivity half of the test is not a pure scan — it needs a traversal (DFS over an adjacency array), since two even-degree components pass parity yet have no single circuit. Note: the splice is a stack operation — the corpus’s home turf — not the pointer wall the search trees hit.