The Hamiltonian
cycle problem is: given a
graph, is there a
simple cycle, where every
vertex is visited
exactly once?
This problem has been proven to be NP-complete for both directed and undirected graphs by a reduction from vertex cover. Related problems are Hamiltonian Path and the Traveling Salesman problem.