A Hamiltonian path is a sequence of distinct vertices in a graph that visits each vertex exactly once. If the path's last vertex is adjacent to its first, it forms a Hamiltonian cycle (also called a Hamiltonian circuit). The concept applies to both undirected and directed graphs: in directed graphs each step must follow the prescribed edge direction, while in undirected graphs edges may be traversed either way. For background on the formal setting, see basic resources on graphs and graph theory.

Key characteristics and distinctions

Hamiltonian paths are concerned with visiting vertices without repetition. This contrasts with Eulerian paths, which are concerned with traversing each edge exactly once; the two notions are independent and have different necessary and sufficient conditions and algorithms. Finding a Hamiltonian path is a decision problem: given a graph, does a Hamiltonian path (or cycle) exist? This decision problem is known to be NP-complete in general, a fact that places it among the class of computationally intractable problems under current complexity assumptions (NP-completeness). For comparison with edge-based traversal problems, see material on Eulerian paths.

Examples and special classes

Certain families of graphs guarantee Hamiltonian behaviour. Complete graphs K_n are Hamiltonian for all n ≥ 3: every ordering of vertices yields a Hamiltonian cycle. Tournaments (orientations of complete graphs) always contain a Hamiltonian path, a result known as Rédei's theorem. Trees are Hamiltonian only if they are paths themselves: a tree with any branching cannot contain a Hamiltonian path visiting every vertex exactly once. There are also classical sufficient conditions that ensure Hamiltonicity in simple graphs:

  • Dirac's theorem: a simple graph on n ≥ 3 vertices is Hamiltonian if every vertex has degree at least n/2.
  • Ore's theorem: if every pair of distinct nonadjacent vertices has degrees summing to at least n, the graph is Hamiltonian.

Algorithms, complexity and practical approaches

Because the general Hamiltonian path problem is NP-complete, no polynomial-time algorithm is known for all graphs. Exact algorithms rely on exponential time in the worst case: notable examples include backtracking and branch-and-bound searches and dynamic programming approaches such as the Held–Karp algorithm for the travelling salesman formulation, which runs in roughly O(n^2 2^n) time and is commonly used as a benchmark for exact solutions. In practice, heuristics, local search, and approximation schemes are used for large instances; the travelling salesman problem (TSP) is the optimization version that seeks the shortest Hamiltonian cycle in a weighted graph and plays a central role in logistics and routing.

History and notable facts

The term "Hamiltonian" derives from William Rowan Hamilton, who devised the Icosian game in the mid-19th century: a puzzle of finding a Hamiltonian cycle on the edge graph of the dodecahedron. His algebraic approach, the Icosian Calculus, paralleled other algebraic innovations of the era. Although Hamilton popularized the idea, earlier work on Hamiltonian cycles in polyhedral graphs had been conducted by Thomas Kirkman. For historical discussions, see references to the Icosian game and the dodecahedron problem (dodecahedron, Icosian Calculus).

Applications and importance

Beyond recreational puzzles, Hamiltonian paths and cycles model routes that must visit a set of locations exactly once: scheduling, vehicle routing, circuit design, and certain combinatorial designs. The travelling salesman problem is a direct optimization outgrowth of Hamiltonian cycle questions and has prompted vast research into algorithms, approximations and complexity theory. Because the decision and optimization versions are computationally demanding, studying structural graph properties that guarantee Hamiltonicity or permit efficient algorithms remains an active area of combinatorics and theoretical computer science.