
> 
> A graph is Hamiltonian if and only if
>  its closure is Hamiltonian.
> 
> 
> 


I am looking for a simple (i.e. short) proof of the theorem, that I can use as part of an article on topological sorting.


I've not been able to find one in the literature I have access to. Any help would be appreciated.



Proof of Bondy and Chvátal Theorem
Let $G=G\_0, G\_1, G\_2$, etc. be a sequence of graphs where each $G\_i$ is formed by performing a single closure step to $G\_{i-1}$ — that is, add an edge $uv$ to $G\_i$ when $u$ and $v$ together have at least $n$ neighbors. If any graph in this sequence is Hamiltonian, let $k$ be the minimum $k$ such that $G\_k$ is Hamiltonian. Then I claim that $k=0$. For, otherwise let $uv$ be the edge added to form $G\_k$ from $G\_{k-1}$ and let $C$ be a Hamiltonian cycle in $G\_k$. There are $n-1$ other edges in $C$, and $n$ edges going out from $u$ and $v$ together, so by the pigeonhole principle there exists an edge $pq$ in $C$ (with the vertex labeling chosen so that $u$ is clockwise of $v$ and $p$ is clockwise of $q$) such that $G\_{k-1}$ contains edges $up$ and $vq$. But then $C + up + vq - pq - uv$ is a Hamiltonian cycle in $G\_{k-1}$ contradicting the assumption that $k>0$.


