Hamiltonian cycle, verifying and finding

Question

If we have an algorithm that in polynomial time says if a graph G has an hamiltonian cycle, can we have an algorithm that in polynomial time find an hamiltonian cycle?

My attempt is to delete an edge of graph G and have G', after run the algorithm on G' to know if it has an hamiltonian cycle if not it means that the edge is in some hamiltonian cycle. Now I don't know how to go on.

Answer 1

Let $P$ be an arbitrary simple path in the graph. If $P$ appears in a Hamiltonian cycle of the graph, you can remove all the vertices of $p$ except the first and the last vertex, connect these two vertices with an edge and the resulting graph must be Hamiltonian.

Keeping this in mind, we can build the Hamiltonian cycle step by step starting with path of length one, since you already described how to build such a path. Then we can extend a path of length $i$ to a path of length $i+1$ using the trick above, where we try all neighbors of the last vertex in the path as a next vertex and we apply the trick above to check if a Hamiltonian cycle exists where the new path is a part of the cycle. Note that we call the black-box at most $m := |E|$ times. Once we reach a path of length $n-3$ it is easy to complete the path into a Hamiltonian cycle in linear time.