Introduction

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.

Hunt the Tour

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">Click the dots in order to build a tour that visits <b>every</b> vertex exactly once and returns to where it started — a <b>Hamiltonian cycle</b>. Stuck? Let the computer <b>Search</b> and watch it backtrack. Below, the <b>Euler check</b> (every edge once) is settled by a single instant rule.</p>
<svg id="graph" viewBox="0 0 320 240" class="graph"></svg>
<div class="status" id="status">Pick a starting dot.</div>
<div class="btns">
  <button id="search" type="button">Search (backtracking)</button>
  <button id="euler" type="button">Euler check</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Hamiltonian cycle: visit every vertex exactly once and return to the start.
// Deciding whether one exists is NP-complete (Karp, 1972). The general method
// is backtracking search: extend a partial tour, hit dead ends, back up.
// Contrast: an Eulerian circuit (every EDGE once) exists iff the graph is
// connected and every vertex has even degree — an instant linear-time rule.
const POS = [ [60,50],[260,50],[160,110],[60,190],[260,190] ];
const NAMES = ['A','B','C','D','E'];
// Adjacency (undirected). This graph HAS a Hamiltonian cycle: A-B-E-C-D-A.
const EDGES = [[0,1],[0,2],[0,3],[1,2],[1,4],[2,3],[2,4],[3,4]];
const ADJ = NAMES.map(()=>[]);
EDGES.forEach(([a,b])=>{ ADJ[a].push(b); ADJ[b].push(a); });
const N = NAMES.length;
const has = (a,b)=> ADJ[a].includes(b);

let tour = []; // sequence of vertex indices the player has clicked

const svg = document.getElementById('graph');
function render(){
  svg.innerHTML = '';
  // edges
  EDGES.forEach(([a,b])=>{
    const used = inTour(a,b);
    const l = document.createElementNS('http://www.w3.org/2000/svg','line');
    l.setAttribute('x1',POS[a][0]); l.setAttribute('y1',POS[a][1]);
    l.setAttribute('x2',POS[b][0]); l.setAttribute('y2',POS[b][1]);
    l.setAttribute('class','edge'+(used?' used':''));
    svg.appendChild(l);
  });
  // nodes
  for(let i=0;i<N;i++){
    const c = document.createElementNS('http://www.w3.org/2000/svg','circle');
    c.setAttribute('cx',POS[i][0]); c.setAttribute('cy',POS[i][1]); c.setAttribute('r',16);
    let cls='node'; if(tour[0]===i) cls+=' start'; else if(tour.includes(i)) cls+=' on';
    c.setAttribute('class',cls);
    c.addEventListener('click',()=>clickNode(i));
    svg.appendChild(c);
    const t = document.createElementNS('http://www.w3.org/2000/svg','text');
    t.setAttribute('x',POS[i][0]); t.setAttribute('y',POS[i][1]+4);
    t.setAttribute('text-anchor','middle'); t.setAttribute('class','label');
    t.textContent = NAMES[i]; svg.appendChild(t);
  }
}
function inTour(a,b){
  for(let i=0;i+1<tour.length;i++){
    if((tour[i]===a&&tour[i+1]===b)||(tour[i]===b&&tour[i+1]===a)) return true;
  }
  // closing edge back to start
  if(tour.length===N && ((tour[N-1]===a&&tour[0]===b)||(tour[N-1]===b&&tour[0]===a))) return true;
  return false;
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

function clickNode(i){
  if(tour.length===0){ tour=[i]; setStatus(fmt('Started at %v%. Move to a neighbour.', { v: NAMES[i] }),''); render(); return; }
  const last = tour[tour.length-1];
  // close the cycle?
  if(tour.length===N && i===tour[0] && has(last,i)){
    render(); setStatus(fmt('✓ Hamiltonian cycle: %map%→%v%', { map: tour.map(x=>NAMES[x]).join('→'), v: NAMES[tour[0]] }),'ok'); return;
  }
  if(tour.includes(i)){ setStatus(fmt('%v% is already visited — each vertex only once.', { v: NAMES[i] }),'bad'); return; }
  if(!has(last,i)){ setStatus(fmt('No edge from %v% to %v2%.', { v: NAMES[last], v2: NAMES[i] }),'bad'); return; }
  tour.push(i); render();
  if(tour.length<N) setStatus(fmt('Visited %map%. Keep going.', { map: tour.map(x=>NAMES[x]).join('→') }),'');
  else setStatus(fmt('All vertices visited — click %v% to close the loop.', { v: NAMES[tour[0]] }),'');
}

// Backtracking search for a Hamiltonian cycle; counts the steps it explores.
function search(){
  let steps=0; const path=[0]; const seen=new Array(N).fill(false); seen[0]=true;
  function dfs(v){
    if(path.length===N) return has(v,0); // can we close back to start?
    for(const w of ADJ[v]){ if(!seen[w]){ steps++; seen[w]=true; path.push(w);
      if(dfs(w)) return true; path.pop(); seen[w]=false; } }
    return false;
  }
  const ok = dfs(0);
  if(ok){ tour=path.slice(); render();
    setStatus(fmt('Found after %steps% extension steps: %map%→%v%', { steps: steps, map: path.map(x=>NAMES[x]).join('→'), v: NAMES[path[0]] }),'ok');
    console.log('Hamiltonian cycle:', path.map(x=>NAMES[x]).join('-'), '| steps', steps);
  } else setStatus('No Hamiltonian cycle exists in this graph.','bad');
}

// Eulerian circuit test: connected + every vertex even degree. Instant.
function euler(){
  const deg = ADJ.map(a=>a.length);
  const odd = deg.filter(d=>d%2!==0).length;
  // connectivity (all non-isolated vertices reachable)
  const seen=new Array(N).fill(false); const st=[0]; seen[0]=true; let cnt=1;
  while(st.length){ const v=st.pop(); for(const w of ADJ[v]) if(!seen[w]){seen[w]=true;cnt++;st.push(w);} }
  const connected = cnt===N;
  if(connected && odd===0) setStatus('Euler: every vertex has even degree → an Eulerian circuit exists. (instant)','ok');
  else setStatus(fmt('Euler: %odd% vertices have odd degree → no Eulerian circuit. (decided in one pass)', { odd: odd }),'bad');
}

document.getElementById('search').addEventListener('click',search);
document.getElementById('euler').addEventListener('click',euler);
document.getElementById('reset').addEventListener('click',()=>{ tour=[]; render(); setStatus('Pick a starting dot.',''); });
render();
Result
Console

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.

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/hamiltonian-cycle/Content licensed under CC BY-NC 4.0.