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.
Euler's breakthrough was to throw away the map and keep only the connections
The exact shape of the river, the length of each bridge, and the walking distance between bridges do not matter. For the puzzle, a landmass is just a vertex and a bridge is just an edge. Once the city is compressed to four vertices and seven edges, the impossibility becomes a degree-counting argument.
Memory hook: enter + leave = two edges
Every ordinary visit to a vertex consumes edges in pairs: one to enter and one to leave. Odd degree therefore creates an unmatched edge. Only the start and end of an open trail are allowed to have one unmatched edge each.
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:
| Graph type | Eulerian circuit exists iff | Eulerian trail exists iff |
|---|---|---|
| Undirected (connected) | every vertex has even degree | exactly 0 or 2 vertices have odd degree |
| Directed (connected) | every vertex has equal in-degree and out-degree | at most one vertex has out-degree − in-degree = 1, at most one has in-degree − out-degree = 1, all others balanced |
The whole undirected Eulerian problem reduces to counting odd-degree vertices
Connectivity aside, you do not need to search through possible walks. Count the odd-degree vertices first. Their number immediately tells you whether an edge-by-edge traversal can close, stay open, or is impossible.
Handshaking Lemma connection: the number of odd-degree vertices is always even, so the possibilities naturally jump from 0 to 2 to 4 or more.
Directed version: replace “even degree” with flow balance. Every time a directed trail enters a vertex, it needs an unused outgoing edge to leave. A circuit therefore needs \(\deg^-(v)=\deg^+(v)\) at every vertex; an open trail may have one start with one extra outgoing edge and one end with one extra incoming edge.
Key Insight
This is a genuinely rare thing in graph theory: a natural, hard-sounding question ("can I traverse every edge exactly once?") with an easy-to-check, fully general, if-and-only-if answer computable in \(O(V+E)\) time just by checking degrees. Compare this to the Hamiltonian question below, which sounds almost identical but has no such easy characterization — one of the most instructive contrasts in the entire field.
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.
Hierholzer works by stitching closed loops together
The important invariant is that in an Eulerian graph you never get stranded at a different vertex: unused incident edges keep arriving and leaving in pairs. So the first walk closes into a cycle. If that cycle misses some edges, start another closed walk from a vertex already on the cycle and splice the new loop into the old one.
Why the runtime is linear: each edge is consumed once and inserted into the final circuit once, so with adjacency lists the total work is \(O(E)\).
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.
Chinese Postman: pay only for the repetitions you cannot avoid
The postal worker is allowed to reuse streets; the optimization question is which streets should be repeated. Odd-degree vertices are exactly where an Eulerian tour fails, so the algorithm pairs those odd vertices as cheaply as possible and duplicates the corresponding shortest paths.
Important distinction
“Duplicate an edge” means traverse that street an extra time; it does not mean physically build another street. The objective is the original total edge cost plus the minimum unavoidable repeat cost.
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.
Euler asks “did I use every edge?” Hamilton asks “did I visit every vertex?”
The two problems sound almost interchangeable until you draw them. An Eulerian circuit may revisit a vertex many times because vertices are not the scarce resource. A Hamiltonian cycle may ignore many edges because only the vertices must each appear exactly once.
Memory hook
Euler = Edges. Hamilton = Homes/vertices. Euler cares about traversing every connection; Hamilton cares about visiting every location.
Fast necessary checks for a Hamiltonian cycle
If a graph has a Hamiltonian cycle, then several things must already be true: it must be connected; every vertex must have degree at least 2; and it cannot have an articulation point, because deleting any one vertex from the Hamiltonian cycle leaves a path connecting all remaining vertices.
These are useful rejection tests, not proofs of existence. Passing all of them only means “a Hamiltonian cycle is still possible.”
A Much Harder Question Than It Sounds
Despite the superficial similarity to the Eulerian question, no known if-and-only-if characterization of Hamiltonian graphs exists, and determining whether a graph has a Hamiltonian cycle is NP-complete (formally proven in Part 22) — believed to have no polynomial-time general algorithm at all. Instead, graph theory offers only sufficient conditions (guarantee a cycle exists, but don't characterize every Hamiltonian graph) and necessary conditions (rule some graphs out, but don't confirm others in).
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.
Dirac and Ore say “dense enough guarantees Hamiltonian” — not “only dense graphs are Hamiltonian”
Think of Dirac and Ore as certificates: if the degree condition passes, you may immediately conclude a Hamiltonian cycle exists. If it fails, you simply lose that certificate and may still need search or another theorem.
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.
Hamiltonian backtracking is “commit, detect a dead end early, undo”
At each step, choose an unvisited neighbor and extend the partial path. If the choice strands an unvisited vertex, repeats a vertex, or eventually cannot return to the start, abandon that branch immediately and try a different choice.
The worst-case search still grows exponentially because many partial paths may need to be tried. Heuristics help by making contradictions appear sooner, but they do not change the general complexity class.
Eulerian vs. Hamiltonian: the comparison worth remembering
| Question | Eulerian | Hamiltonian |
|---|---|---|
| Must cover | Every edge exactly once | Every vertex exactly once |
| What may happen | Vertices may repeat; edges may not be skipped | Edges may be skipped; vertices may not repeat |
| Existence test | Complete degree characterization | No simple complete characterization known |
| Construction | Hierholzer in \(O(E)\) | General search can be exponential |
| Classic optimization cousin | Chinese Postman | Traveling Salesperson |
Exercises
- 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.
- Construct a graph with a Hamiltonian cycle that satisfies neither Dirac's nor Ore's theorem, demonstrating that these are sufficient, not necessary, conditions.
- 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).
- 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.
Next in the Series
In Part 13: Graph Coloring, we meet the chromatic number, Brooks' and Vizing's theorems, and the controversial 1976 computer-assisted proof of the Four Color Theorem.