Is finding a hamiltonian cycle as hard as determining if one exists?

Question

Is finding a hamiltonian cycle as hard as determining if one exists? Can a hamiltonian cycle be found in polynomial time given an oracle for detecting hamiltonian cycles?

Answer 1

Assume you have a method to detect whether or not a graph $G$ with $v$ vertices and $e$ edges has a Hamiltonian cycle in time $p(v,e)$ for some polynomial $p$. The following method then actually finds such a cycle:

For each edge: Remove the edge; check if the graph is still Hamiltonian; if not, add the edge back, otherwise leave it deleted. Once we have treated all edges, a cycle remains.

This makes $e$ tests of time $\le p(v,e)$ each, hence the time is $\le e\cdot p(v,e)$ and still polynomial.