Can you visit every point in a network without ever crossing your own path?
In short: A Hamiltonian path traces a route through a graph that visits every vertex exactly once. While the concept sounds simple, determining if such a path exists in a complex network is a notoriously difficult computational problem. It is a puzzle that has captivated mathematicians from 9th-century India to Victorian Ireland.
The concept is named after William Rowan Hamilton, who in 1856 introduced the icosian game. This challenge required players to find a Hamiltonian cycle—a closed loop visiting every vertex exactly once—on the edges of a dodecahedron. Hamilton solved this using his own icosian calculus, an algebraic structure related to his invention of quaternions. However, his specific method was limited and did not apply to arbitrary graphs.
Long before Hamilton, the problem appeared in various forms. In the 9th century, scholars like Rudrata in India and al-Adli ar-Rumi in Islamic mathematics explored the knight's tour, a specific instance of finding a Hamiltonian path on a chessboard. By the 18th century, figures such as Abraham de Moivre and Leonhard Euler were also publishing work on these tours. Even Thomas Kirkman studied Hamiltonian cycles in polyhedra a year before Hamilton’s formal work, providing a counterexample of a polyhedron that lacked such a cycle.
Modern graph theory classifies these structures rigorously. A graph containing a Hamiltonian path is called traceable, while one with a cycle is Hamiltonian. Identifying these paths is computationally demanding, as the problem is NP-complete. To simplify, mathematicians developed degree-based characterizations. In 1952, G. A. Dirac provided early sufficient conditions, later generalized by the 1972 Bondy–Chvátal theorem, which examines a graph's closure to determine if it must be Hamiltonian. These theorems essentially prove that if a graph is sufficiently dense with edges, it is guaranteed to contain a Hamiltonian cycle.
The study of these paths extends into diverse mathematical domains, including the analysis of tournaments, platonic solids, and Cayley graphs of finite Coxeter groups, all of which are known to be Hamiltonian. While any Hamiltonian cycle can become a path by removing an edge, the reverse is only true if the path's endpoints are adjacent. This distinction remains central to understanding the connectivity and structural integrity of complex networks.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Hamiltonian path
To cite this card, link to https://intellectplus.co.uk/app/science-hamiltonian-path.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Discrete mathematics · More in Science · Latest · A–Z · All topics