TOPICS
Search

Hamiltonian Path

A Hamiltonian path, also called a Hamilton path, is a graph path that visits each vertex of a graph exactly once (Knuth 2025, p. 1). The counts in this entry exclude paths of length 0, so a one-vertex graph has count 0. For a path visiting at least three vertices, an edge joining its endpoints closes it into a Hamiltonian cycle (or Hamilton cycle).

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

In general, the problem of determining whether a graph has a Hamiltonian path is NP-complete (Garey and Johnson 1983, pp. 199-200).

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 and |_x_| is the floor function. 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"], with both orientations of paths 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 over all nonisomorphic 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 distinct vertices i and j can be found using an algorithm for Hamiltonian cycles. Add a new vertex z adjacent only to i and j. The augmented graph has a Hamiltonian cycle iff the original graph has a Hamiltonian path from i to j. Deleting z from such a cycle gives the desired path. Alternatively, for graphs on at least three vertices, add the edge (i,j) if necessary and require a Hamiltonian cycle that uses that edge. An arbitrary Hamiltonian cycle may avoid (i,j) and does not certify a Hamiltonian path with those endpoints.

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. The index of each value list in the table starts at 1. An X indicates that the family in that row is not defined for the corresponding parameter value. The counts exclude paths of length 0 even when the cited OEIS sequence includes a one-vertex path, as in OEIS A120443. The counts for the crown graph are half the directed counts in OEIS A137886.

graphOEISsequence
Andrásfai graphA3079321, 5, 72, 3047, 265034, 42442251, ...
antiprism graphA307933X, X, 120, 408, 1200, 3240, 8330, 20720, ...
barbell graphA0010441, 1, 4, 36, 576, 14400, ...
(n,n)-black bishop graphA3079340, 1, 4, 96, 25376, 32132352, ...
cocktail party graph K_(n×2)A3079350, 4, 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 graphA1378860, 0, 6, 72, 1920, 69120, ...
cycle graph C_nA000027X, X, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
folded cube graphA307948X, 1, 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_n0, 1006080, ...
(n,n)-king graphA3081290, 12, 392, 171592, 364618672, ...
(n,n)-knight graphA3081310, 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 graphA3081410, 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 graphX, X, X, X, X, 808668610560, ...
torus grid graph C_n square C_nA268838X, X, 756, 45696, 2955700, 560028096, ...
transposition graphA3079490, 1, 36, 27267618816, ...
triangular graphA308142X, 0, 3, 120, 47760, ...
triangular grid graphA3081443, 12, 114, 1968, 66312, 4381020, 578266212, ...
wheel graph W_nA046092X, X, X, 12, 24, 40, 60, 84, 112, 144, ...
(n,n)-white bishop graphA308146X, 1, 4, 96, 12256, 32132352, 392007078912, ...

Closed forms for the undirected counts for some of these classes of graphs are summarized in the following table. The formulas for the complete graph and path graph apply for n>=2, and the formula for the ladder graph applies for n>=2, with the exceptional count 1 for n=1. The barbell and complete-bipartite formulas apply for n>=1, and the cocktail-party and 2n-crossed-prism formulas for n>=2. The cycle, gear, Möbius-ladder, prism, and sun formulas require n>=3, and the wheel formula requires n>=4.

graphformula
barbell graph[(n-1)!]^2
cocktail party graph K_(n×2)1/2(2n)!_1F_1(-n;-2n;-2)
complete graph K_n1/2n!
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. The antiprism recurrence is conjectural for n>=12 (OEIS A307933). The crown and prism recurrences apply for n>=6 and n>=9, respectively.

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." §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." Pre-Fascicle 8A of The Art of Computer Programming, Vol. 4. Draft, pp. 1-3, Dec. 4, 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. Math. Soc. 71, 583-592, 2024. https://doi.org/10.1090/noti2907.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 A000027, A001044, A001710, A002378, A003682, A005843, A006070/M5295, A020875, A033996, A046092, A057427, A091299, A096969, A096970, A120443, A124350, A124352, A137886, A137890, A137892, A158664, A165134, A171386, A193346, A193352, A233826, A246957, A259212, A268838, A284673, A301559, A307932, A307933, A307934, A307935, A307936, A307948, A307949, A308129, A308130, A308131, A308132, A308134, A308136, A308137, A308138, A308139, A308141, A308142, A308144, A308146, and A308586 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