CentralNotice Hamiltonian path From Wikipedia, the free encyclopedia Jump to: navigation , search This article is about the overall graph theory concept of a Hamiltonian path. For the specific problem of determining whether a Hamiltonian path or cycle exists in a given graph, see Hamiltonian path problem . A Hamiltonian cycle in a dodecahedron . Like all platonic solids , the dodecahedron is Hamiltonian. The Herschel graph is the smallest possible polyhedral graph that does not have a Hamiltonian cycle. In the mathematical field of graph theory , a Hamiltonian path (or traceable path ) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit ) is a Hamiltonian path that is a cycle . Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem , which is NP-com...