Question:
Prove a simple graph $G$ is Hamiltonian if and only if its closure is Hamiltonian.
$|V(G)|=n$, $\deg(u)+\deg(v)\ge n$ ($u$ and $v$ is a pair of non-adjacent vertices on $G$)
I know if $G$ is Hamiltonian, its closure must be Hamiltonian.
However, I don't know how to prove $G$ is Hamiltonian when its closure is Hamiltonian.
I got stuck! Any ideas?
[update]
Quote from Scott's reply:
"Suppose that $x_i$ is adjacent to $u$ ...show that if $x_{i+1}$ were adjacent to $v$ in $G_k$, we could modify $C$ to get a Hamilton circuit in $G_k$. "
_____________ | | v--x2--x3--...--xi xi+1--..--u |_____________________|
The word is really important, so I drew the diagram and hope it is useful for someone.
Also from the diagram, we can understand why it supposes $x_{i+1}$ is adjacent to $v$ instead of $x_i$.