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 -Hypercube is 2, 8, 96, 43008, ... (Sloane's A006069; Gardner 1986, pp. 23-24).

**References**

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.''
http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S.
*The Encyclopedia of Integer Sequences.* San Diego: Academic Press, 1995.

© 1996-9

1999-05-25