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.