In
graph theory, a Hamilton
circuit is a
path through a graph that visits each
vertex in the
graph exactly once, and ends at the beginning vertex. The concept of the Hamilton circuit comes from a puzzle invented in 1857 by the Irish mathematician
Sir William Rowan Hamilton. Hamilton's puzzle consisted of a wooden
dodecahedron with a peg at each vertex of the dodecahedron, and string. The 20 verticies of the dodecahedron were labeled with different cities in the world. The object of the puzzle was to start at a city and travel along the edges of the dodecahedron, visiting each of the other 19 cities exactly once, and end back at the first city. The circuit traveled was marked off using the stings and pegs.
The problem of finding a Hamilton circuit in a given graph is considered to be NP-Complete.
Source: Discrete Mathematics and Its Applications