# 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?

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.

• You need to come up with an algorithm that can find a Hamiltonian cycle in polynomial time, given a polynomial time algorithm to determine whether any graph has an Hamiltonian path. Hint: What happens when we remove a vertex from the graph? Jan 25, 2018 at 14:44
• @Discretelizard we may have several connected components
– Yos
Jan 25, 2018 at 14:47
• @Yos No in Hamiltonian path or cycle is defined for connected graph only Jan 25, 2018 at 15:22

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.