History and Terminology > Wolfram Language Commands >
Discrete Mathematics > Graph Theory > Circuits >
Interactive Entries > Interactive Demonstrations >

Hamiltonian Cycle

DOWNLOAD Mathematica Notebook

A Hamiltonian cycle, also called a Hamiltonian circuit, Hamilton cycle, or Hamilton circuit, is a graph cycle (i.e., closed loop) through a graph that visits each node exactly once (Skiena 1990, p. 196). A graph possessing a Hamiltonian cycle is said to be a Hamiltonian graph. By convention, the singleton graph K_1 is considered to be Hamiltonian even though it does not posses a Hamiltonian cycle, while the connected graph on two nodes K_2 is not.

The Hamiltonian cycle is named after Sir William Rowan Hamilton, who devised a puzzle in which such a path along the polyhedron edges of an dodecahedron was sought (the Icosian game).

A Hamiltonian cycle of a graph can be computed efficiently in the Wolfram Language using FindHamiltonianCycle[g][[All, All, 1]][[1]] (where the cycle returned is not necessarily the lexicographically first one). All simple (undirected) cycles of a graph can be computed time-efficiently (but with a memory overhead of more than 10 times that needed to represent the actual cycles) using Sort[FindHamiltonianCycle[g, All][[All, All, 1]]]. (Note the cycles returned are not necessarily returned in sorted order by default.) Possible Method options to FindHamiltonianCycle include "Backtrack", "Heuristic", "AngluinValiant", "Martello", and "MultiPath". In addition, the Wolfram Language command FindShortestTour[g] attempts to find a shortest tour, which is a Hamiltonian cycle (with initial vertex repeated at the end) for a Hamiltonian graph G if it returns a list with first element equal to the vertex count of G.

Precomputed lists of Hamiltonian cycles for many named graphs can be obtained using GraphData[graph, "HamiltonianCycles"]. Precomputed counts of the corresponding number of Hamiltonian cycles may similarly be obtained using GraphData[graph, "HamiltonianCycleCount"]..

The total numbers of directed Hamiltonian cycles for all simple graphs of orders n=1, 2, ... are 0, 0, 2, 10, 58, 616, 9932, 333386, 25153932, 4548577688, ... (OEIS A124964).

In general, the problem of finding a Hamiltonian cycle is NP-complete (Karp 1972; Garey and Johnson 1983, p. 199), so the only known way to determine whether a given general graph has a Hamiltonian cycle is to undertake an exhaustive search. 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.

HamiltonianTetrahedronHamiltonianOctahedronHamiltonianCubeHamiltonianDodecahedronHamiltonianIcosahedron
HamiltonianPlatonicCycles

All Platonic solids are Hamiltonian (Gardner 1957), as illustrated above.

Khomenko and Golovko (1972) gave a formula giving the number of graph cycles of any length, but its computation requires computing and performing matrix operations involving all subsets up to size n-2, making it computationally expensive. A greatly simplified and improved version of the Khomenko and Golovko formula for the special case of n-cycles (i.e., Hamiltonian cycles) gives

c_n=1/(2n)sum_(i=2)^n(-1)^(n-i)sum_(|S|=n-i)Tr(A_S^n),

where A_S^k is the kth matrix power of the submatrix of the adjacency matrix A with the subset S of rows and columns deleted (Perepechko and Voropaev).

The following table summarizes the numbers of (directed) Hamiltonian cycles on various classes of graphs. The n-hypercube is considered by Gardner (1986, pp. 23-24), who however gives the counts for an n-hypercube for n=1, 2, ... as 2, 8, 96, 43008, ... (OEIS A006069) which must be divided by 2^n to get the number of distinct circuits counting shifts of points as equivalent regardless of starting vertex.

graphSloanesequence
Andrásfai graphA1432490, 2, 10, 290, 17394, 2218778, 473405802, ...
antiprism graphA124353X, X, 32, 58, 112, 220, 450, 938, 1982, 4220, 9022, ...
(n,n)-black bishop graphA282889X, X, 0, 8, 1408, 1106016, , 27605259264, 3564317860276224, ...
cocktail party graphA1293480, 2, 32, 1488, 112512, ...
complete bipartite graph K_(n,n)A1432480, 2, 12, 144, 2880, 86400, 3628800, ...
complete tripartite graph K_(n,n,n)A1411472, 32, 3168, 926208, 59857920, ...
complete graph K_nA1243550, 0, 2, 6, 24, 120, 720, 5040, 40320, 362880, ...
2n-crossed prism graphA007283X, X, X, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, ...
crown graphA0940472, 12, 312, 9600, 416880, 23879520, 1749363840, ...
cube-connected cycleA000000X, X, 12, 57256, ...
cycle graph C_nA007395X, X, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...
folded cube graphA280847X, 0, 6, 144, 47520, 664024227840, ...
grid graph P_n square P_nA1432460, 2, 0, 12, 0, 2144, 0, 9277152, 0, ...
grid graph P_n square P_n square P_nA0000000, 12, 0, ?, 0, ...
halved cube graphA2812550, 0, 6, 1488, 1973918880, 625659743022644718120960, ...
hypercube graph Q_nA0030420, 2, 12, 2688, 1813091520, ...
(n,n)-king graphA140521X, 6, 32, 5660, 4924128, 45707720232, ...
(n,n)-knight graphA000000X, 0, 0, 0, 0, 19724, 0, 26534728821064, ...
n-ladder graphA0000000, 2, 2, 2, 2, 2, 2, ...
Möbius ladderA124356X, X, X, 12, 10, 16, 14, 20, 18, 24, 22, 28, 26, 32, 30, ...
Mycielski graphA1432470, 2, 20, 204620, ...
odd graphA000000X, 2, 0, 2838528, ...
permutation star graphA0000000, 0, 2, 36, ...
prism graph Y_nA124349X, X, 6, 12, 10, 16, 14, 20, 18, 24, 22, 28, 26, 32, ...
(n,n)-queen graphA1586630, 6, 3920, 804728540, 79483492253499328, ...
rook graph K_n square K_nA000000X, 2, 96, 568224, 335750676480, ...
sun graphA000000X, X, 2, 2, 2, 2, 2, 2, ...
sunlet graphA000000X, X, 0, 0, 0, 0, 0, 0, ...
torus grid graph C_n square C_nA000000X, X, 96, 2688, 47160, 6546720, ...
transposition graphA0000000, 0, 12, 1139736576, ...
triangular graphA129349X, 0, 2, 32, 6432, 19497984, ...
triangular grid graphA1745892, 2, 6, 52, 948, 34428, 1371454, ...
web graphA000000X, X, 0, 0, 0, 0, 0, ...
wheel graph W_nA005843X, X, X, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, ...
(n,n)-white bishop graphA282890X, X, 2, 8, 792, 1106016, 9403200256, 3564317860276224, ...

Closed forms for some of these classes of graphs are summarized in the following table, where alpha, beta, and gamma are the roots of x^3-x^2-2x-1 and K_x(x) is a modified Bessel function of the second kind.

n-antiprism graph for n>=32(2n+alpha^n+beta^n+gamma^n)
n-cocktail party graph for n>=2(2n-1)!_1F_1(-n,1-2n;-2)
complete graph K_n for n>=3(n-1)!
complete bipartite graph K_(n,n) for n>=2n!(n-1)!
complete tripartite graph K_(n,n,n) for n>=22^n(n-1)!(n!)2_3F_2(1/2(n-1),-1/2n,n;1,1,1)
2n-crossed prism graph for n>=23·2^n
n-crown graph for n>=32(-1)^n(n-1)!+n!sum_(j=0)^(n-1)(-1)^j(n-j-1)!(2n-j-1; j)
=(n-1)!nint(2ne^(-2)K_n(2))
cycle graph C_n for n>=32
Hanoi graph2
n-ladder graph2
n-Möbius ladder for n>=32[2+n-(-1)^n]
prism graph Y_n for n>=32[(-1)^n+n+1]
n-sun graph for n>=32
wheel graph W_n for n>=42(n-1)

Wolfram Web Resources

Mathematica »

The #1 tool for creating Demonstrations and anything technical.

 Wolfram|Alpha »

Explore anything with the first computational knowledge engine.

 Wolfram Demonstrations Project »

Explore thousands of free applications across science, mathematics, engineering, technology, business, art, finance, social sciences, and more.
Computerbasedmath.org »

Join the initiative for modernizing math education.

 Online Integral Calculator »

Solve integrals with Wolfram|Alpha.

 Step-by-step Solutions »

Walk through homework problems step-by-step from beginning to end. Hints help you try the next step on your own.
Wolfram Problem Generator »

Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.

 Wolfram Education Portal »

Collection of teaching and learning tools built by Wolfram education experts: dynamic textbook, lesson plans, widgets, interactive Demonstrations, and more.

 Wolfram Language »

Knowledge-based programming for everyone.