How to Prove a Simple Graph is Hamiltonian If and Only If Its Closure is Hamiltonian

Question

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

Answer 1

Consider the construction of $\operatorname{cl}(G)$ from $G$. At each stage you add an edge $uv$ such that $\deg(u)+\deg(v)\ge n$. Say the stages are $G_0=G,G_1,\dots,G_m=\operatorname{cl}(G)$. Show that if $G_{k+1}$ is Hamiltonian, then so is $G_k$. Then from the hypothesis that $\operatorname{cl}(G)$ is Hamiltonian it will follow that $G_{m-1},G_{m-2},\dots,G_0=G$ are all Hamiltonian, and in particular that $G$ is Hamiltonian.

To get you started, suppose that $G_{k+1}$ is Hamiltonian, with Hamilton circuit $C$, and $G_k$ is not Hamiltonian. Let $uv$ be the edge added to get $G_{k+1}$ from $G_k$; clearly $C$ must include $uv$. Say $C$ is $v,x_2,x_3,\dots,x_{n-1},u$, where $x_2,\dots,x_{n-1}$ are the other $n-2$ vertices of $G$.

1. Suppose that $x_i$ is adjacent to $u$ in $G_k$ for some $i<n-1$; 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$. Thus, if $x_i$ is adjacent to $u$, $x_{i+1}$ cannot be adjacent to $v$.

2. Use (1) to show that $\deg_{G_k}(u)+\deg_{G_k}(v)<n$ and so derive a contradiction.

Answer 2

Case 1: If G is non Hamiltonian graph.by adding any extra edge without loss of any generality we get a maximal non Hamiltonian graph(by definition of maximal non Hamiltonian graph) then graph G is Hamiltonian. Case 2:If possible suppose graph is non-Hamiltonian. If there is path passing through every vertex of G $ V_1 \rightarrow V_2\rightarrow......V_i\rightarrow.....V_n $ $ V_1$&$V_n$ are not adjacent by hypothesis $deg(u)+deg(v) \geq n\\ \\ \\ \\ \\$ $\exists$ some i $V_1$ and adjacent to $V_i$ and $V_n$ adjacent to $V_{i-1}$ this produce a Hamiltonian cycle as follows: $V_1 \rightarrow V_2 \rightarrow....V_i \rightarrow V_{i+1} \rightarrow.....V_n \rightarrow V_{i-1} \rightarrow....V_1$ Which is contradiction.

$\therefore$Our supposition is wrong

$\therefore$ Graph G is Hamiltonian