Euler vs Hamilton

In 1736, the city of Königsberg had seven bridges, and its citizens amused themselves with a question: could you take a walk that crosses every bridge exactly once? Leonhard Euler proved you couldn't — and in doing so invented graph theory. His rule is almost insultingly simple, and we still use it today.

Now change one word. Instead of "cross every bridge once," ask: can you take a tour that visits every city exactly once? This is the Hamiltonian question, named for the mathematician William Rowan Hamilton.

The two puzzles look like twins. Both live on the same dots-and-lines diagram — a graph. Both ask for a single unbroken path. Yet one is among the easiest problems in computer science and the other is among the hardest. That gap is not an accident of phrasing. It is one of the cleanest windows we have into what makes a problem hard.

Below is one small graph. Press Euler check and the answer pops out instantly from a single rule: an Euler trail (every edge once) exists exactly when at most two vertices have an odd number of edges. No searching, no trying — just count.

<p class="hint">{{hint}}</p>
<svg id="graph" viewBox="0 0 320 220" role="img" aria-label="{{aria_graph}}"></svg>
<div class="status" id="status">{{pick_question}}</div>
<div class="btns">
  <button id="euler" type="button">{{btn_euler}}</button>
  <button id="hamilton" type="button">{{btn_hamilton}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
svg { width: 100%; max-width: 340px; height: auto; display: block; margin: .2rem auto; }
.edge { stroke: #adb1b8; stroke-width: 3; }
.edge.lit { stroke: #1d3557; stroke-width: 5; }
.node circle { fill: #e8eef3; stroke: #1d3557; stroke-width: 2; }
.node.lit circle { fill: #1d3557; }
.node text { font: 700 13px ui-monospace, monospace; fill: #1d3557; text-anchor: middle; dominant-baseline: central; }
.node.lit text { fill: #fff; }
.status { font-size: .98rem; font-weight: 600; margin: .5rem 0; min-height: 2.6em; line-height: 1.4; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Now press Find Hamilton path. The same graph, but now we want to visit every vertex once. There is no magic rule. The computer has to try orderings of the vertices until one works, and the number of orderings explodes as the graph grows. Watch the "paths tried" counter — that is the difference between easy and hard, made visible on identical-looking puzzles.

Here is the precise picture — and it is genuinely surprising.

• Eulerian path is in P. Euler's 1736 theorem says a connected graph has an Euler trail if and only if zero or exactly two vertices have odd degree. Checking that is a single pass over the graph, and building the trail (Hierholzer's algorithm) is linear time. Solvable, fast, settled for almost three centuries.
• Hamiltonian path is NP-complete. Deciding whether any path visits every vertex exactly once was one of Richard Karp's original 21 NP-complete problems in 1972. No algorithm is known that is fundamentally faster than searching, and finding one would resolve P vs NP.
• Checking stays easy on both. Hand me a proposed path and I can verify it in seconds either way. The asymmetry is entirely about finding a Hamiltonian path, not checking one — the very signature of NP.

The lesson is humbling: difficulty does not live in how a problem looks. "Every edge once" and "every vertex once" differ by a single noun, yet one is a closed chapter and the other is a frontier we still cannot cross.

Both puzzles escaped the textbook long ago — and you can feel the difficulty gap in real budgets.

• Euler (the easy cousin): covering every street once powers snowplow and street-sweeper routing, mail and meter-reading rounds, and drone inspection of power lines. This is the Route Inspection / Chinese Postman problem, and it stays efficient.
• Hamilton (the hard cousin): visiting every stop once is the heart of delivery and field-service routing and is the core of the Traveling Salesman Problem. DNA fragment assembly was once modeled this way too.
• Knowing which one you have is the whole game. Reframe a task as "cover every edge" and it is tractable; phrase it as "visit every vertex" and you may be stuck with heuristics forever. Engineers fight hard to land on the Euler side of the line.

The same hard core reappears across routing, scheduling and bioinformatics — it is the difference between a solved problem and a perpetual approximation.

Euler vs Hamilton is the perfect cautionary tale. Two questions on the same graph, separated by a single word — edge versus vertex — and yet one is a one-line rule from 1736 while the other has resisted every assault since 1972.

It is a reminder that you cannot judge a problem by its cover. Hardness lives in the deep structure of a question, not its surface. The next time a task looks "basically the same" as one you've solved, remember Königsberg: the gap between every edge once and every vertex once is the gap between trivial and intractable — and no one yet knows how to close it.