Part 12: Eulerian & Hamiltonian Graphs

The Seven Bridges of Königsberg

In 1736, the city of Königsberg (in Prussia, now Kaliningrad) straddled the Pregel River, its two islands and two mainland banks connected by seven bridges. A popular local puzzle asked: could a resident walk through the city crossing each of the seven bridges exactly once, returning to the start? Swiss mathematician Leonhard Euler proved the answer was no — and in doing so, in a paper titled "Solutio problematis ad geometriam situs pertinentis" ("The solution of a problem relating to the geometry of position"), he abstracted the city into four landmasses (vertices) and seven bridges (edges), invented the very idea of representing a physical layout as an abstract network, and is now credited with writing the first paper in the history of graph theory.

flowchart LR
    A((Island A)) ===|"2 bridges"| B((Island B))
    A ---|"1 bridge"| N((North Bank))
    A ---|"1 bridge"| S((South Bank))
    B ---|"1 bridge"| N
    B ---|"1 bridge"| S
            

Euler's key insight, stated in modern language: every time a walk passes through a vertex (not starting or ending there), it uses up exactly two incident edges — one in, one out. So a vertex with odd degree can only ever be a starting or ending point of the walk, never a "pass-through." Königsberg's four landmasses all had odd degree (3, 3, 3, 5) — far more than the at-most-two odd-degree vertices a single walk could accommodate. No such walk could possibly exist.

Eulerian Trails and Circuits

An Eulerian circuit is a closed walk using every edge exactly once and returning to its start; an Eulerian trail relaxes this to allow different start and end vertices. Euler's argument generalizes into a clean, complete characterization:

Hierholzer's Algorithm (Preview)

Knowing an Eulerian circuit exists is one thing; constructing one is another. Hierholzer's algorithm (published posthumously in 1873, after German mathematician Carl Hierholzer's early death) does so in \(O(E)\): walk arbitrarily until stuck (which can only happen back at the start, given the even-degree condition), then find any vertex on that closed walk with unused edges, splice in a new closed sub-walk from there, and repeat until every edge is used. We cover the full algorithm and code in an upcoming deep-dive batch.

The Chinese Postman Problem

What if a graph isn't Eulerian, but you still need to traverse every edge at least once, at minimum total cost — the exact situation of a postal worker delivering mail down every street? This is the Chinese Postman Problem (also called the Route Inspection Problem), named for Chinese mathematician Guan Meigu (also romanized as Mei-Ko Kwan), who first studied it in 1962 while working on street-sweeping optimization. The solution strategy: Eulerize the graph by duplicating a minimum-weight set of edges to make every vertex's degree even, then run Hierholzer's algorithm on the resulting Eulerian multigraph. Finding that minimum-weight duplication set reduces to a minimum-weight perfect matching among the graph's odd-degree vertices — a problem we revisit in Part 16.

Hamiltonian Paths and Cycles

A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle does so and returns to the start. Named for Irish mathematician Sir William Rowan Hamilton, who in 1857 commercialized the idea as the Icosian Game — a puzzle played on a wooden dodecahedron where pegs marked cities and players had to find a route touching every city exactly once along the polyhedron's edges, sold as a parlor game nearly a century before "Hamiltonian cycle" became standard mathematical terminology.

Dirac's and Ore's Theorems

Dirac's theorem (Gabriel Andrew Dirac, 1952 — a stepson of the physicist Paul Dirac): if every vertex in a simple graph on \(n \geq 3\) vertices has degree at least \(n/2\), the graph has a Hamiltonian cycle. Ore's theorem (Øystein Ore, 1960) generalizes this: if every pair of non-adjacent vertices has degree sum at least \(n\), a Hamiltonian cycle exists (Dirac's theorem follows as a special case, since every vertex having degree \(\geq n/2\) implies every non-adjacent pair sums to at least \(n\)). Both are purely sufficient conditions — plenty of Hamiltonian graphs satisfy neither.

Finding a Hamiltonian cycle in practice (when one exists but no easy degree condition applies) typically falls back to backtracking search: build a partial path vertex by vertex, backtrack the moment no valid extension exists, and use pruning heuristics (like preferring low-degree vertices first) to cut the search space — exponential in the worst case, but often fast enough in practice for moderately sized graphs.

Exercises

1. Add one bridge to the Königsberg graph (your choice of which two landmasses to connect) so that an Eulerian trail (not necessarily a circuit) becomes possible. Verify using the degree condition table.
2. Construct a graph with a Hamiltonian cycle that satisfies neither Dirac's nor Ore's theorem, demonstrating that these are sufficient, not necessary, conditions.
3. Explain why \(K_{n,n}\) with \(n \geq 2\) always has a Hamiltonian cycle, but \(K_{n,n+2}\) never does (hint: think about what a Hamiltonian cycle in a bipartite graph must alternate between).
4. Challenge: Implement backtracking search for Hamiltonian cycles, and test it on a graph satisfying Ore's theorem (confirming a cycle is found) versus a bipartite graph like \(K_{3,5}\) (confirming the search correctly reports none exists).

Conclusion & Next Steps

We've now traced graph theory back to its literal origin — Euler's 1736 proof — and seen the sharp line between "traverse every edge" (fully characterized, efficiently solvable) and "visit every vertex" (only partial sufficient conditions, believed intractable in general). That same edge-vs-vertex distinction reappears as our next topic: coloring vertices so that no edge connects two of the same color.