How to efficiently find a Hamiltonian cycle in a graph whose closure is complete? 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
 A: 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)$.
A: In the case that your graph satisfies the conditions of Ore's theorem (so that it's Ore closure is $K_n$ after 'one step'), there is an easy algorithm to find a Hamilton cycle.  
Arbitrarily arrange the vertices $v_1, \dots, v_n$ in a circle.  If all consecutive vertices $v_i$ and $v_{i+1}$ are adjacent in $G$ (subscripts are read mod $n$), then we are done.  Otherwise, if $v_i$ and $v_{i+1}$ are non-adjacent, find an index $j$ such that $v_i$ is adjacent to $v_j$ and $v_{i+1}$ is adjacent to $v_{j+1}$.  Such an index $j$ is guaranteed to exist by Ore's condition, and can be found in time $O(n)$.  Change the ordering of the vertices in the obvious way, and note that the number of non-adjacent consecutive vertices has gone down.  After at most $n$ steps, we will output a Hamilton cycle, so this takes $O(n^2)$ in total.   
