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.

  • $\begingroup$ 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? $\endgroup$
    – Discrete lizard
    Jan 25, 2018 at 14:44
  • $\begingroup$ @Discretelizard we may have several connected components $\endgroup$
    – Yos
    Jan 25, 2018 at 14:47
  • 1
    $\begingroup$ @Yos No in Hamiltonian path or cycle is defined for connected graph only $\endgroup$
    – Complexity
    Jan 25, 2018 at 15:22

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.