Complexity Explorer Santa Few Institute

Hamiltonian Path

In graph theory, a Hamiltonian path is a path – or trace – through a graph that visits each vertex (node) exactly once. If the beginning and ending vertices are adjacent, the path is known as a Hamiltonian cycle. A graph that contains a Hamiltonian path is a traceable graph.

Hamiltonian paths are named after Sir William Rowan Hamilton, an Irish mathematician and astronomer. He developed the icosion game in which players were to find a Hamiltonian cycle in the edges of a dodecahedron.

In the interactive below, you can click your way through a two-dimensional planar dodecahedron graph to trace a Hamiltonian path. Reset the game using the "refresh" arrow.