Let G be a graph, and let P be a Hamiltonian path of G. Does G contain a Hamiltonian cycle? Even though this problem may seem simpler than HC, it is just as difficult: knowing the Hamiltonian path P does not help to decide if the graph G is Hamiltonian, as the following result due to Papadimitriou and Steiglitz [PaSt77] shows.
