A Hamiltonian graph, also called a Hamilton graph, is a graph possessing a Hamiltonian cycle (Knuth 2025, p. 2). A graph that is not Hamiltonian is said to be nonhamiltonian.
A Hamiltonian graph on 
nodes has graph
circumference 
.
A graph possessing exactly one Hamiltonian cycle is known as a uniquely Hamiltonian graph.
While it would be easy to make a general definition of "Hamiltonian" that considers the singleton graph 
to be either Hamiltonian or nonhamiltonian, defining "Hamiltonian"
to mean "has a Hamiltonian cycle" and taking "Hamiltonian cycles"
to be a subset of "cycles" in general would lead to the convention that
the singleton graph is nonhamiltonian (B. McKay,
pers. comm., Oct. 11, 2006). However, by convention, the singleton
graph is generally considered to be Hamiltonian (B. McKay, pers. comm.,
Mar. 22, 2007). The convention in this work and in GraphData
is that 
is Hamiltonian, while 
is nonhamiltonian.
The numbers of simple Hamiltonian graphs on 
nodes for 
, 2, ... are then given by 1, 0, 1, 3, 8, 48, 383, 6196,
177083, ... (OEIS A003216), the first few of
which are illustrated above.
A graph can be tested to see if it is Hamiltonian in the Wolfram Language using HamiltonianGraphQ[g].
Testing whether a graph is Hamiltonian is an NP-complete problem (Skiena 1990, p. 196). Rubin (1974) describes an efficient search procedure that can find some or all Hamiltonian paths and Hamiltonian cycles in a graph using deductions that greatly reduce backtracking and guesswork.
All Hamiltonian graphs on at least three vertices are biconnected, although the converse is not true (Skiena 1990, p. 197). A bipartite graph on at least two vertices with bipartition classes of unequal sizes is not Hamiltonian, since any Hamiltonian cycle would have to alternate between the two classes. Equal bipartition sizes are not sufficient for Hamiltonicity; for example, the E graph and H graph have equal bipartition sizes but are not Hamiltonian.
If a simple graph 
on 
vertices satisfies 
for every pair of nonadjacent
vertices 
and 
, where 
is the vertex degree of
,
then 
is Hamiltonian (Ore 1960; Skiena 1990, p. 197).
All planar 4-connected graphs have Hamiltonian cycles, but not all polyhedral graphs do. For example, the smallest polyhedral graph that is not Hamiltonian is the Herschel graph on 11 nodes.
All Platonic solids are Hamiltonian (Gardner 1957), as illustrated above.
Although not explicitly stated by Gardner (1957), all Archimedean solids have Hamiltonian cycles as well, several of which are illustrated above. However, the skeletons of the Archimedean duals (i.e., the Archimedean dual graphs) are not necessarily Hamiltonian, as shown by Coxeter (1946) and Rosenthal (1946) for the rhombic dodecahedron (Gardner 1984, p. 98).
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).
Zhan (2026) proved that a biconnected graph 
is Hamiltonian when its independence
number 
equals its graph radius 
. If 
is 3-connected, the same
equality implies that it is both Hamilton-connected
and pancyclic. Zhan (2026) acknowledges ChatGPT
assistance in developing and checking the proofs.
