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 
is considered to be Hamiltonian
even though it does not possess a Hamiltonian cycle, while the connected graph on
two nodes 
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).
The problem of enumerating Hamiltonian cycles in specific classes of graphs is one of the most difficult problems in enumerative combinatorics (Krasko et al. 2017).
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 
if it returns a list with first element
equal to the vertex count of 
.
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 
, 2, ... are 0, 0, 2, 10, 58, 616,
9932, 333386, 25153932, 4548577688, ... (OEIS A124964).
A graph possessing exactly one Hamiltonian cycle is known as a uniquely Hamiltonian graph.
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.
All Platonic solids are Hamiltonian (Gardner 1957), as illustrated above.
There are exactly five known connected nonhamiltonian vertex-transitive graphs, namely the path graph 
, the Petersen
graph 
,
the Coxeter graph 
, the triangle-replaced Petersen, and the triangle-replaced Coxeter graph. As attributed by Gould (1991) citing
Bermond (1979), Thomassen conjectured that all other connected vertex-transitive graphs are Hamiltonian
(cf. Godsil and Royle 2001, p. 45; Mütze 2024).
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 
, making it computationally expensive. A greatly simplified
and improved version of the Khomenko and Golovko formula for the special case of
-cycles
(i.e., Hamiltonian cycles) gives
 |
where 
is the 
th
matrix power of the submatrix of the adjacency matrix 
with the subset 
of rows and columns deleted and 
is the matrix trace (Perepechko
and Voropaev).
The following table summarizes the numbers of (undirected) Hamiltonian cycles on various classes of graphs. The 
-hypercube is considered by Gardner
(1986, pp. 23-24), who however gives the counts for an 
-hypercube for 
, 2, ... as 2, 8, 96, 43008, ... (OEIS A006069)
which must be divided by 
to get the number of distinct (directed) cycles counting
shifts of points as equivalent regardless of starting vertex. Dixon and Goodman (1975)
considered Hamiltonian cycles in hypercube graphs,
and Krasko et al. (2017) considered Hamiltonian cycles in complete 
-partite graphs 
.
| graph | OEIS | sequence |
| Andrásfai graph | A307902 | 0, 1, 5, 145, 8697, 1109389, 236702901, ... |
| antiprism graph | A306447 | X, X, 16, 29, 56, 110, 225, 469, 991, 2110, 4511, ... |
 -black bishop graph | A307920 | X, X, 0, 4, 704, 553008, , 13802629632, 1782158930138112, ... |
cocktail party graph  | A307923 | 0, 1, 16, 744, 56256, ... |
complete graph  | A001710 | 0, 0, 1, 3, 12, 60, 360, 2520, 20160, 181440, ... |
complete bipartite graph  | A010796 | 0, 1, 6, 72, 1440, 43200, 1814400, ... |
complete k-partite graph  | A381326 | 3, 744, 1833840, 18872165376, 553245728256000, ... |
complete tripartite graph  | A307924 | 1, 16, 1584, 463104, 29928960, ... |
 -crossed
prism graph | A007283 | X, X, X, 6, 12, 24, 48, 96, 192, 384, 768, 1536, ... |
| crown graph | A306496 | 1, 6, 156, 4800, 208440, 11939760, 874681920, ... |
| cube-connected cycle graph | A000000 | X, X, 6, 28628, ... |
cycle
graph  | A000012 | X, X, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... |
| folded cube graph | A307925 | X, 0, 3, 72, 23760, 332012113920, ... |
grid graph  | A003763 | 0, 1, 0, 6, 0, 1072, 0, 4638576, 0, ... |
grid graph  | A000000 | 0, 6, 0, ?, 0, ... |
| halved cube graph | A307926 | 0, 0, 3, 744, 986959440, 312829871511322359060480, ... |
hypercube graph  | A066037 | 0, 1, 6, 1344, 906545760, ... |
 -king graph | A140519 | X, 3, 16, 2830, 2462064, 22853860116, ... |
 -knight
graph | A001230 | X, 0, 0, 0, 0, 9862, 0, 13267364410532, ... |
 -ladder graph | A057427 | 0, 1, 1, 1, 1, 1, 1, ... |
| Möbius ladder | A103889 | X, X, X, 6, 5, 8, 7, 10, 9, 12, 11, 14, 13, 16, 15, ... |
| Mycielski graph | A307927 | 0, 1, 10, 102310, ... |
| odd graph | A301557 | X, 1, 0, 1419264, ... |
| permutation star graph | A000000 | 0, 0, 1, 18, ... |
prism
graph  | A103889 | X, X, 3, 6, 5, 8, 7, 10, 9, 12, 11, 14, 13, 16, ... |
 -queen
graph | A307928 | 0, 3, 1960, 402364270, 39741746126749664, ... |
rook graph  | A269561 | X, 1, 48, 284112, 167875338240, ... |
| sun graph | A000012 | X, X, 1, 1, 1, 1, 1, 1, ... |
torus grid graph  | A222199 | X, X, 48, 1344, 23580, 3273360, ... |
| transposition graph | A307896 | 0, 0, 6, 569868288, ... |
| triangular graph | A307930 | X, 0, 1, 16, 3216, 9748992, ... |
| triangular grid graph | A112676 | 1, 1, 3, 26, 474, 17214, 685727, ... |
wheel
graph  | A000027 | X, X, X, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ... |
 -white
bishop graph | A307929 | X, X, 1, 4, 396, 553008, 4701600128, 1782158930138112, ... |
Closed forms for some of these classes of graphs are summarized in the following table, where 
,
,
and 
are the roots of 
and 
is a modified Bessel function
of the second kind.
-
-Cube." Proc. Amer. Math. Soc. 50, 500-504,
1975.Gardner, M. "Mathematical Games: About the Remarkable Similarity
between the Icosian Game and the Towers of Hanoi." Sci. Amer. 196,
150-156, May 1957.Gardner, M. 
-Partite
Graphs." Math. Slovaca 29, 43-47, 1979.Karp, R. M.
"Reducibility Among Combinatorial Problems." In Complexity of Computer
Computations (Ed. R. E. Miller and J. W. Thatcher). New York:
Plenum Press, pp. 85-103, 1972.Khomenko, N. P. and Golovko,
L. D. "Identifying Certain Types of Parts of a Graph and Computing Their
Number." Ukr. Math. J. 24, 313-321, 1972.Kocay, W.
"An Extension of the Multi-Path Algorithm for Hamilton Cycles." Disc.
Math. 101, 171-188, 1992.Kocay, W. and Li, B. "An Algorithm
for Finding a Long Path in a Graph." Util. Math. 45, 169-185,
1994.Krasko, E.; Labutin, I.; and Omelchenko, A. "Enumeration of
Labelled and Unlabelled Hamiltonian Cycles in Complete 
-partite Graphs." 1 Sep 2017.