Hamiltonian Cycle

Picture a map of cities joined by roads. You want a round trip that passes through every city exactly once and ends back where it started. That route is called a Hamiltonian cycle, named after the 19th‑century mathematician William Rowan Hamilton.

It sounds almost identical to a puzzle that schoolchildren solve in seconds: can you trace a figure without lifting your pencil, walking along every road exactly once? That second one is the Eulerian circuit, and Leonhard Euler settled it in 1736 with a rule so simple you can check it at a glance.

Swap a single word — every road becomes every city — and the difficulty explodes. One of these puzzles is among the easiest in graph theory. The other is among the hardest problems we know.

Here is a small graph. Click the dots in order to trace a tour that visits every vertex exactly once and returns to the start. When you are stuck, press Search and watch the computer try paths and backtrack down dead ends.

<p class="hint">{{hint}}</p>
<svg id="graph" viewBox="0 0 320 240" class="graph"></svg>
<div class="status" id="status">{{pick_start}}</div>
<div class="btns">
  <button id="search" type="button">{{btn_search}}</button>
  <button id="euler" type="button">{{btn_euler}}</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; }
.graph { width: 100%; max-width: 360px; height: auto; display: block; margin: .2rem auto .4rem;
         background: #f4f7fa; border: 1px solid #dde5ec; border-radius: 10px; }
.edge { stroke: #b7c4d0; stroke-width: 2.5; }
.edge.used { stroke: #1d3557; stroke-width: 4; }
.node { fill: #c9ccd1; stroke: #8a9099; stroke-width: 2; cursor: pointer; transition: all .12s; }
.node:hover { fill: #aeb4bc; }
.node.on { fill: #1d3557; stroke: #142845; }
.node.start { fill: #e63946; stroke: #c92f3c; }
.label { font: 700 13px ui-monospace, monospace; fill: #1d3557; pointer-events: none; }
.node.on + .label, .node.start + .label { fill: #fff; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.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

Notice the contrast. The Euler check at the bottom is instant: just confirm the graph is connected and every vertex touches an even number of edges — that one rule decides it. The Hamiltonian search has no such shortcut. The computer must try partial tours, hit dead ends, and back up, and the number of tours to explore grows explosively as you add vertices.

Why are two such similar puzzles so different?

• Eulerian circuit (every edge once): easy. Euler's 1736 theorem says a connected graph has one exactly when every vertex has an even degree. You can verify that in a single pass — linear time — so the whole problem is solved before you even start walking.
• Hamiltonian cycle (every vertex once): NP-complete. In 1972 Richard Karp placed it on his famous list of 21 NP-complete problems. There is no known efficient test; the best general methods still amount to searching through tours, and that search can blow up exponentially.
• Checking is still easy. Hand someone a claimed tour and they can verify it in seconds — that is exactly what makes the problem sit in NP. The hard part is finding the tour, or proving none exists.
• It powers a famous cousin. Add distances to the edges and "shortest Hamiltonian cycle" becomes the Traveling Salesman Problem, the poster child of hard optimization.

So the gap between the two puzzles is not a quirk of wording — it is a real instance of the divide behind P vs NP. One word decides whether you have a quick rule or an exponential hunt.

"Pass through every point exactly once" is a shape that shows up far beyond puzzle books:

• Routing and logistics: a vehicle that must visit every stop once and return to base is hunting a Hamiltonian cycle — usually the shortest one, the Traveling Salesman Problem.
• Manufacturing: a drill that must punch every hole on a circuit board, or a laser cutting every part, wants a single efficient tour over all the points.
• Genome assembly: stitching DNA fragments back into a chromosome was once modeled as a Hamiltonian path — and that hardness pushed biologists toward the easier Eulerian formulation instead.
• DNA computing: Leonard Adleman's 1994 landmark experiment solved a small Hamiltonian path instance using actual strands of DNA in a test tube.

Learn why the Hamiltonian cycle is hard and you have met the heart of routing, sequencing and tour problems — and the same constraint engine behind SAT.

The Hamiltonian cycle teaches one of the sharpest lessons in computer science. Euler's "every edge once" puzzle is decided by a one-line rule you can check in a single pass. Hamilton's "every vertex once" looks just as innocent, yet it is NP-complete — no shortcut is known, and finding the tour may require searching a sea of possibilities.

So the next time a problem looks easy because a famous-sounding cousin is, look closer. The line between a quick rule and an exponential hunt can hinge on a single word — and crossing it lands you squarely in P vs NP.