A graph whose closure is the complete graph is Hamiltonian by the Bondy-Chvátal theorem, but I haven't found a polynomial algorithm for finding a Hamiltonian cycle in such a graph. Is there one that we know of?


<https://en.wikipedia.org/wiki/Bondy%E2%80%93Chv%C3%A1tal_theorem#Bondy.E2.80.93Chv.C3.A1tal_theorem>


I don't see that class here <http://www.graphclasses.org/classes/problem_Hamiltonian_cycle.html>



How to efficiently find a Hamiltonian cycle in a graph whose closure is complete?
Tony's method works in the general case. Let $e\_1, e\_2, \ldots, e\_N$ be the edges that are added to $G$, in the order they are added, to make the complete graph. Choose an arbitrary hamiltonian cycle in the complete graph. Now remove $e\_N$. If $e\_N$ was in the cycle, you can find a new cycle that avoids it by the cross-over technique that Tony explains. Then remove $e\_{N-1}$ in the same way. Continue until you removed all the edges that were added. Since each step takes time $O(n)$, the total time is $O(nN)=O(n^3)$. I don't believe this is best possible and wouldn't be surprised if this can be implemented in time $O(n^2)$.


