Hamiltonian Path

A Hamiltonian Path in a graph is a path that contains each vertex in exactly once. If it ends at the vertex it started at it is a Hamiltonian Circuit.

A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian Circuit.