If there's algorithm which returns true if Hamiltonian cycle exists in polynomial time then an algorithm to find the cycle in such time also exists?

Question

How can it be proved that if there's an algorithm which in polynomial time determines whether a graph has a Hamiltonian cycle then there's an algorithm which can find such Hamiltonian cycle in polynomial time as well?

Note: there's no need to devise the actual algorithm I just need to prove that one causes the other to hold.

I thought that perhaps the algorithm A which just determines whether the graph contains a Hamiltonian cycle has to perform the same amount of work as the algorithm B which has to find the actual cycle because each node has to be visited.

But I'm not sure how to actually prove this.

Answer 1

Input: A graph G = (V, E) for which the checker algorithm is true.

if you remove an edge $e\in E$ from The graph and run the algorithm then if it returns false the removed edge must be part of every hamiltonian cycle in the graph.

If the result is true then we can remove the edge and remove another edge we haven't checked yet and run the algorithm again.

Eventually the graph will only contain a hamiltonian cycle. in O(e) applications of the algorithm.