TOPICS
Search

Hamiltonian Path

A Hamiltonian path, also called a Hamilton path, is a graph path between two vertices of a graph that visits each vertex exactly once. If a Hamiltonian path exists whose endpoints are adjacent, then the resulting graph cycle is called a Hamiltonian cycle (or Hamiltonian cycle).

A graph that possesses a Hamiltonian path is called a traceable graph.

In general, the problem of finding a Hamiltonian path is NP-complete (Garey and Johnson 1983, pp. 199-200), so the only known way to determine whether a given general graph has a Hamiltonian path is to undertake an exhaustive search

If a bipartite graph has bipartition classes X and Y, then any Hamiltonian path alternates between X and Y, so ||X|-|Y||<=1 is necessary. In particular, a connected bipartite graph whose bipartition classes differ in size by more than 1 is untraceable. The converse does not hold in general; examples with bipartition sizes differing by 0 that are untraceable include the E graph and H graph, and examples with sizes differing by 1 that are untraceable include the fork graph and spoke graph S(3,2).

More generally, if a graph G on n vertices has a Hamiltonian path, then every other edge of the path gives a matching of size |_n/2_|. Thus traceability requires nu(G)=|_n/2_|, where nu(G) is the matching number. Equivalently, a graph with nu(G)<|_n/2_| is untraceable.

Finding a single Hamiltonian path of a graph g is implemented in the Wolfram Language as FindHamiltonianPath[g]. A precomputed list of all Hamiltonian paths for many named graphs can be obtained using GraphData[graph, "HamiltonianPaths"], where and both orientations of paths are included (so that {1, 2, 3} is considered distinct from {3, 2, 1}). A precomputed count of the corresponding number of Hamiltonian paths is given by GraphData[graph, "HamiltonianPathCount"].

The total numbers of directed Hamiltonian paths for all simple graphs of orders n=1, 2, ... are 0, 2, 8, 50, 416, 5616, 117308, 4862736, ... (OEIS A193352).

Rubin (1974) describes an efficient search procedure that can find some or all Hamilton paths and circuits in a graph using deductions that greatly reduce backtracking and guesswork. A probabilistic algorithm due to Angluin and Valiant (1979), described by Wilf (1994), can also be useful to find Hamiltonian cycles and paths. A Hamiltonian path between two vertices i and j can be found if an algorithm for Hamiltonian cycles is available. This can be done by checking if the original graph G contains the edge (i,j) and adding it if not to obtain G^'. Since a Hamiltonian path with adjacent endpoints is a Hamiltonian cycle and since i and j are now adjacent, finding a Hamiltonian cycle and splitting at the edge gives a Hamiltonian path from i to j in G. Similarly, if no Hamiltonian cycle exists in G^', then there is no Hamiltonian path from i to j in G.

The Lovász conjecture states that without exception, every connected vertex-transitive graph is traceable.

The following table summarizes the numbers of (undirected) Hamiltonian paths on various classes of graphs.

graphOEISsequence
Andrásfai graphA3079321, 5, 72, 3047, 265034, 42442251, ...
antiprism graphA307933X, X, 120, 408, 1200, 3240, 8330, 20720, ...
barbell graphA001044X, X, 4, 36, 576, 14400, ...
(n,n)-black bishop graphA307934X, X, X, 96, 25376, 32132352, ...
cocktail party graph K_(n×2)A3079354, 120, 6912, 631680, ...
complete graph K_nA0017100, 1, 3, 12, 60, 360, ...
complete bipartite graph K_(n,n)A0010441, 4, 36, 576, 14400, ...
complete tripartite graph K_(n,n,n)A3079363, 120, 18792, 7547904, ...
crossed prism graphA308136X, X, X, 72, X, 288, X, 960, X, 2880, ...
crown graphA259212X, X, 6, 72, 1920, 69120, ...
cycle graph C_nA000027X, X, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
folded cube graphA3079481, 12, 576, 1006080, 28102446858240, ...
gear graphA002378X, X, 12, 20, 30, 42, 56, 72, 90, 110, ...
grid graph P_n square P_nA1204430, 4, 20, 276, 4324, 229348, 13535280, ...
grid graph P_n square P_n square P_nA3085860, 72, 2480304, ...
halved cube graphA3081300, 1, 12, 6912, 23710679040, ...
Hanoi graphA3081343, 18, 192, 2730, ...
hypercube graph Q_nA2846731, 4, 72, 45696, 93749829120, ...
Keller graph K_nA0000000, 1006080, ...
(n,n)-king graphA308129X, 12, 392, 171592, 364618672, ...
(n,n)-knight graphA308131X, 0, 0, 0, 864, 3318960, 82787609160, ...
ladder graph P_2 square P_nA0036821, 4, 8, 14, 22, 32, 44, 58, 74, 92, ...
Möbius ladderA020875X, X, 36, 72, 140, 228, 364, 528, 756, ...
Mycielski graphA3081320, 1, 5, 490, 31629560, ...
odd graphA3015590, 3, 120, 328345920, ...
path graph P_nA0574270, 1, 1, 1, 1, 1, 1, 1, ...
prism graph Y_nA308137X, X, 30, 72, 130, 228, 350, 528, ...
(n,n)-queen graphA3081390, 12, 22928, 10221735256, ...
(n,n)-rook graphA3081411/2, 4, 756, 11197440, ...
Sierpiński carpet graphA3081388, 137728, ...
Sierpiński gasket graphA2469573, 12, 552, 6978816, 429714433137180672, ...
star graphA1713860, 1, 1, 0, 0, 0, 0, 0, ...
sun graphA002378X, X, 12, 20, 30, 42, 56, 72, 90, 110, ...
tetrahedral Johnson graphA000000X, X, X, X, X, 808668610560, ...
torus grid graph C_n square C_nA268838X, X, 756, 45696, 2955700, 560028096, ...
transposition graphA3079490, 1, 36, 27267618816, ...
triangular graphA3081420, 3, 120, 47760, ...
triangular grid graphA3081443, 12, 114, 1968, 66312, 4381020, 57826621, ...
wheel graph W_nA046092X, X, X, 12, 24, 40, 60, 84, 112, 144, ...
(n,n)-white bishop graphA308146X, X, X, 96, 12256, 32132352, 392007078912, ...

Closed forms for some of these classes of graphs are summarized in the following table.

graphformula
barbell graph[(n-1)!]^2
cocktail party graph K_(n×2)(2n)!_1F_1(-n;-2n;-2)
complete graph K_nn!
complete bipartite graph K_(n,n)(n!)^2
2n-crossed prism graph6·2^(n-1)n(n+1)
cycle graph C_nn
gear graphn(n+1)
ladder graph P_2 square P_nn^2-n+2
Möbius ladder M_n1/2(-1)^nn[-1+(-1)^n(5+2n^2)]
path graph P_n1
prism graph Y_n1/2n[3+(-1)^n+2n^2]
sun graphn(n+1)
wheel graph W_n2(n-1)(n-2)

Recurrence relations for the number of directed Hamiltonian paths for some graph families are summarized below.

graphorderrecurrence
antiprism graph9a_n=a_(n-9)+a_(n-8)-3a_(n-7)-5a_(n-6)+5a_(n-5)+7a_(n-4)-4a_(n-3)-6a_(n-2)+5a_(n-1)
crown graph3a_n=n(n-1)^2a_(n-2)+(n-2)n(n-1)a_(n-3)+n(n-1)a_(n-1)
prism graph Y_n6a_n=-a_(n-6)+2a_(n-5)+a_(n-4)-4a_(n-3)+a_(n-2)+2a_(n-1)

See also

Graph Cycle, Graph Path, Hamiltonian Cycle, Hamiltonian Graph, Hamiltonian Walk, Longest Path, Lovász Conjecture, Pósa Rotation, Tournament, Traceable Graph

Explore with Wolfram|Alpha

References

Angluin, D. and Valiant, L. "Probabilistic Algorithms for Hamiltonian Circuits and Matchings." J. Comput. Sys. Sci. 18, 155-190, 1979.Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, p. 199, 1983.Godsil, C. and Royle, G. "Hamilton Paths and Cycles." C§3.6 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 45-47, 2001.Gould, R. J. "Updating the Hamiltonian Problem--A Survey." J. Graph Th. 15, 121-157, 1991.Knuth, D. E. "Hamiltonian Paths and Cycles." Volume 4, Pre-Fascicle 8A in The Art of Computer Programming. Draft. Aug. 19, 2025. https://www-cs-faculty.stanford.edu/~knuth/fasc8a.pdf.Mütze, T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems." Not. Amer. Soc. 74, 583-592, 2024.Rubin, F. "A Search Procedure for Hamilton Paths and Circuits." J. ACM 21, 576-580, 1974.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 175, 1990.Sloane, N. J. A. Sequences A005843, A006070/M5295, A033996, A046092, A091299, A096969, A096970, A124350, A124352, A137890, A137892, A158664, A165134, A193346, and A233826 in "The On-Line Encyclopedia of Integer Sequences."Wilf, H. S. Algorithms and Complexity. pp. 120-122. Summer, 1994. https://www2.math.upenn.edu/~wilf/AlgoComp.pdf.

Referenced on Wolfram|Alpha

Hamiltonian Path

Cite this as:

Weisstein, Eric W. "Hamiltonian Path." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/HamiltonianPath.html

Subject classifications