# Does knowing a graph has a Hamiltonian Cycle make it easier to find the cycle?

Given a simple and connected graph $$G=(V, E)$$. I know it's NP-Complete to determine if $$G$$ has a Hamiltonian Cycle (HC). But if we know $$G$$ indeed contains an HC, can we find the cycle in poly-time?

If it were so, then there would be a concrete polynomial $$p$$ that bounded the running time of such an algorithm. Therefore you would be able to detect whether a graph has a Hamiltonian cycle by lying to the algorithm: Claim that the graph has a Hamiltonian cycle, run it for $$p(n)$$ steps, and then check whether by then it has printed a correct cycle or not.