info prev up next book cdrom email home

Hamiltonian Circuit

A closed loop through a Graph that visits each node exactly once and ends adjacent to the initial point. The Hamiltonian circuit is named after Sir William Rowan Hamilton, who devised a puzzle in which such a path along the Edges of an Icosahedron was sought (the Icosian Game).

All Platonic Solids have a Hamiltonian circuit, as do planar 4-connected graphs. However, the problem of finding a Hamiltonian circuit is NP-Complete, so the only known way to determine whether a given general Graph has a Hamiltonian circuit is to undertake an exhaustive search. The number of Hamiltonian circuits on an $n$-Hypercube is 2, 8, 96, 43008, ... (Sloane's A006069; Gardner 1986, pp. 23-24).

See also Chvátal's Theorem, Dirac's Theorem, Euler Graph, Grinberg Formula, Hamiltonian Graph, Hamiltonian Path, Icosian Game, Kozyrev-Grinberg Theory, Ore's Theorem, Pósa's Theorem, Smith's Network Theorem


Chartrand, G. Introductory Graph Theory. New York: Dover, p. 68, 1985.

Gardner, M. ``The Binary Gray Code.'' In Knotted Doughnuts and Other Mathematical Entertainments. New York: W. H. Freeman, pp. 23-24, 1986.

Sloane, N. J. A. Sequence A006069/M1903 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

© 1996-9 Eric W. Weisstein