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