The Hamiltonian Problem

Graph Theory · Axiom Academy

Can you visit every vertex exactly once and return home? Click on vertices in order to create a path. Your goal: visit every vertex exactly once, then return to your starting point. In 1857, Sir William Rowan Hamilton invented a puzzle based on a dodecahedron. Try to find a Hamiltonian cycle on this pentagonal graph (representing one face of his puzzle). You may have encountered Eulerian paths before. Let's see how these two concepts differ! Visits every edge exactly once Easy to check: look at vertex degrees Visits every vertex exactly once Edges can be repeated (or skipped) Very hard to check - no simple rule! Try to find a Hamiltonian cycle in this graph. Some graphs have them, others don't - and there's no easy way to tell! Think you can't find one? That's because this graph has no Hamiltonian cycle! Unlike Eulerian paths, we can't just look at degrees to determine this. We'd have to try all possible paths - an exponential problem! The Hamiltonian problem asks: can we visit every vertex in a graph exactly once and return home? This simple question leads to one of the hardest problems in computer science. Unlike Eulerian paths (check vertex degrees), there's no simple test for Hamiltonian cycles. We can't just look at local properties - we need to consider global structure. This isn't just theoretical! The Traveling Salesman Problem (finding the shortest Hamiltonian cycle) appears in logistics, circuit design, DNA sequencing, and countless optimization problems.

This is the written version of the interactive lesson above. See the full Graph Theory course.