Introduction

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.

Try It

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">One graph, two questions. <b>Euler:</b> can you trace every <i>edge</i> exactly once? (Answered instantly by a degree rule.) <b>Hamilton:</b> can you visit every <i>vertex</i> exactly once? (No rule — the computer must search.)</p>
<svg id="graph" viewBox="0 0 320 220" role="img" aria-label="graph"></svg>
<div class="status" id="status">Pick a question below.</div>
<div class="btns">
  <button id="euler" type="button">Euler check</button>
  <button id="hamilton" type="button">Find Hamilton path</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; }
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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A small graph. Vertices 0..4 with fixed positions; EDGES are undirected pairs.
// EULER: an Euler trail (every edge once) exists iff the graph is connected and
//   the number of odd-degree vertices is 0 or 2 (Euler, 1736) — a one-pass count.
// HAMILTON: a Hamiltonian path (every vertex once) — no shortcut rule is known;
//   we brute-force permutations of the vertices (NP-complete, Karp 1972).
const POS = [[60,40],[260,40],[160,110],[60,180],[260,180]];
const LABEL = ['A','B','C','D','E'];
// Edges chosen so: degrees -> A:2 B:2 C:4 D:2 E:2  => 0 odd vertices => Euler circuit exists.
// And a Hamiltonian path A-B-C-D... we will let the search discover one.
const EDGES = [[0,1],[0,2],[1,2],[2,3],[2,4],[3,4]];
const N = 5;

function degrees(){ const d=Array(N).fill(0); for(const [a,b] of EDGES){ d[a]++; d[b]++; } return d; }
function connected(){
  const seen=new Set([0]); const st=[0];
  while(st.length){ const v=st.pop();
    for(const [a,b] of EDGES){ if(a===v&&!seen.has(b)){seen.add(b);st.push(b);} if(b===v&&!seen.has(a)){seen.add(a);st.push(a);} } }
  return seen.size===N;
}
function adj(a,b){ return EDGES.some(([x,y])=>(x===a&&y===b)||(x===b&&y===a)); }

function draw(litNodes, litEdges){
  const g=document.getElementById('graph'); g.innerHTML='';
  litEdges = litEdges||new Set(); litNodes = litNodes||new Set();
  EDGES.forEach(([a,b],i)=>{
    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'+(litEdges.has(i)?' lit':'')); g.appendChild(l);
  });
  for(let v=0;v<N;v++){
    const grp=document.createElementNS('http://www.w3.org/2000/svg','g');
    grp.setAttribute('class','node'+(litNodes.has(v)?' lit':''));
    const c=document.createElementNS('http://www.w3.org/2000/svg','circle');
    c.setAttribute('cx',POS[v][0]); c.setAttribute('cy',POS[v][1]); c.setAttribute('r',16); grp.appendChild(c);
    const t=document.createElementNS('http://www.w3.org/2000/svg','text');
    t.setAttribute('x',POS[v][0]); t.setAttribute('y',POS[v][1]); t.textContent=LABEL[v]; grp.appendChild(t);
    g.appendChild(grp);
  }
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.innerHTML=t; s.className='status '+(cls||''); }

function euler(){
  const d=degrees(); const odd=d.filter(x=>x%2===1).length;
  const ok = connected() && (odd===0||odd===2);
  draw(new Set(), new Set(EDGES.map((_,i)=>i)));
  const degTxt = d.map((x,i)=>LABEL[i]+'='+x).join(', ');
  if(ok) setStatus(fmt('✓ Euler trail EXISTS. Degrees: %degTxt%. Odd-degree vertices: %odd% (≤2). One count, instant answer — this is in P.', { degTxt: degTxt, odd: odd }) + " ",'ok');
  else setStatus(fmt('✗ No Euler trail. Degrees: %degTxt%. Odd-degree vertices: %odd% (must be 0 or 2).', { degTxt: degTxt, odd: odd }),'bad');
}

// Brute-force Hamiltonian path: try permutations until consecutive vertices are adjacent.
function permute(arr){ if(arr.length<=1) return [arr]; const out=[];
  for(let i=0;i<arr.length;i++){ const rest=arr.slice(0,i).concat(arr.slice(i+1));
    for(const p of permute(rest)) out.push([arr[i]].concat(p)); } return out; }
function hamilton(){
  // Try orderings in an unbiased sequence so the search visibly does work
  // before stumbling on a valid path (the answer is found, just not for free).
  const perms=permute([1,3,0,4,2]); let tried=0, found=null;
  for(const p of perms){ tried++; let ok=true;
    for(let i=0;i<p.length-1;i++){ if(!adj(p[i],p[i+1])){ ok=false; break; } }
    if(ok){ found=p; break; } }
  if(found){
    const litE=new Set();
    for(let i=0;i<found.length-1;i++){ const a=found[i],b=found[i+1];
      EDGES.forEach(([x,y],idx)=>{ if((x===a&&y===b)||(x===b&&y===a)) litE.add(idx); }); }
    draw(new Set(found), litE);
    setStatus(fmt('✓ Hamiltonian path: %map%. Found after trying <b><b>%tried%</b></b> of %length% orderings. No rule — only search.', { map: found.map(v=>LABEL[v]).join(' → '), tried: tried, length: perms.length }),'ok');
    console.log('Hamiltonian path', found.map(v=>LABEL[v]).join(''), '| tried', tried, 'of', perms.length);
  } else setStatus(fmt('✗ No Hamiltonian path exists, after trying all %length% orderings.', { length: perms.length }),'bad');
}

document.getElementById('euler').addEventListener('click',euler);
document.getElementById('hamilton').addEventListener('click',hamilton);
document.getElementById('reset').addEventListener('click',()=>{ draw(); setStatus('Pick a question below.',''); });
draw();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/euler-vs-hamilton/Content licensed under CC BY-NC 4.0.