WOLFRAM

Wolfram Language & System Documentation Center

HamiltonianGraphQ[g]

yields True if the graph g is Hamiltonian, and False otherwise.

Details
Details and Options Details and Options
Examples  
Basic Examples  
Scope  
Applications  
Properties & Relations  
See Also
Related Guides
History
Cite this Page

HamiltonianGraphQ

HamiltonianGraphQ[g]

yields True if the graph g is Hamiltonian, and False otherwise.

Details

  • A graph is Hamiltonian if it has a cycle that traverses each vertex exactly once.

Examples

open all close all

Basic Examples  (2)

Test whether a graph is Hamiltonian:

Wolfram Language code: GraphData[{"Antiprism", 4}]
Wolfram Language code: HamiltonianGraphQ[%]

Not all graphs have a Hamiltonian cycle:

Wolfram Language code: PetersenGraph[5, 2]
Wolfram Language code: HamiltonianGraphQ[%]

Scope  (6)

HamiltonianGraphQ works with undirected graphs:

Wolfram Language code: HamiltonianGraphQ[[image]]

Directed graphs:

Wolfram Language code: HamiltonianGraphQ[[image]]

Multigraphs:

Wolfram Language code: HamiltonianGraphQ[[image]]

Mixed graphs:

Wolfram Language code: HamiltonianGraphQ[[image]]

HamiltonianGraphQ gives False for expressions that are not graphs:

Wolfram Language code: HamiltonianGraphQ[x]

HamiltonianGraphQ works with large graphs:

Wolfram Language code: g = CompleteGraph[10000];
Wolfram Language code: HamiltonianGraphQ[g]//Timing

Applications  (2)

Test whether the Icosian game [MathWorld] has a solution:

Wolfram Language code: g = PolyhedronData["Dodecahedron", "Skeleton"]
Wolfram Language code: HamiltonianGraphQ[g]

A Hamiltonian cycle:

Wolfram Language code: h = PathGraph[First[FindHamiltonianCycle[g]]];
Wolfram Language code: Row[{HighlightGraph[g, h, GraphHighlightStyle -> "Thick"], Graphics3D[{Opacity[.8], PolyhedronData["Dodecahedron", "GraphicsComplex"], Red, Tube[PolyhedronData["Dodecahedron", "Vertices", "Coordinates"][[Append[VertexList[h], VertexList[h][[1]]]]], 0.1]}]}, Spacer[10]]

Test whether there is a sequence of moves by a knight chess piece that visits each square of an chessboard exactly once:

Wolfram Language code: g = KnightTourGraph[8, 8];
Wolfram Language code: HamiltonianGraphQ[g]

Properties & Relations  (4)

A Hamiltonian cycle can be found using FindHamiltonianCycle:

Wolfram Language code: GraphData[{"Antiprism", 4}]
Wolfram Language code: FindHamiltonianCycle[%]

Skeleton graphs of platonic solids are Hamiltonian:

Wolfram Language code: PolyhedronData["Platonic"]
Wolfram Language code: PolyhedronData[#, "Skeleton"] & /@ %
Wolfram Language code: HamiltonianGraphQ /@ %

The line graph of a Hamiltonian graph is Hamiltonian:

Wolfram Language code: {CompleteGraph[4], LineGraph[CompleteGraph[4]]}
Wolfram Language code: HamiltonianGraphQ /@ %

An Eulerian graph is not always Hamiltonian:

Wolfram Language code: g = Graph[{12, 23, 31, 34, 45, 53}]
Wolfram Language code: EulerianGraphQ[g]
Wolfram Language code: HamiltonianGraphQ[g]

The line graph of an Eulerian graph is Hamiltonian:

Wolfram Language code: HamiltonianGraphQ[LineGraph[g]]
Wolfram Research (2010), HamiltonianGraphQ, Wolfram Language function, https://reference.wolfram.com/language/ref/HamiltonianGraphQ.html.

Text

Wolfram Research (2010), HamiltonianGraphQ, Wolfram Language function, https://reference.wolfram.com/language/ref/HamiltonianGraphQ.html.

CMS

Wolfram Language. 2010. "HamiltonianGraphQ." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/HamiltonianGraphQ.html.

APA

Wolfram Language. (2010). HamiltonianGraphQ. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/HamiltonianGraphQ.html

BibTeX

@misc{reference.wolfram_2026_hamiltoniangraphq, author="Wolfram Research", title="{HamiltonianGraphQ}", year="2010", howpublished="\url{https://reference.wolfram.com/language/ref/HamiltonianGraphQ.html}", note=[Accessed: 12-June-2026]}

BibLaTeX

@online{reference.wolfram_2026_hamiltoniangraphq, organization={Wolfram Research}, title={HamiltonianGraphQ}, year={2010}, url={https://reference.wolfram.com/language/ref/HamiltonianGraphQ.html}, note=[Accessed: 12-June-2026]}