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.