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.
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$.
Let me restate the theorem for variables.
Notation Read $p\bowtie q$ as "$p$ is adjacent to $q$", and $p\not\bowtie q$ as "$p$ is not adjacent to $q$".
Theorem Let $G$ be a graph whose order is greater than $2$. Let $v_1$ and $v_2$ be vertices such that $v_1\neq v_2 \land v_1\not\bowtie v_2$ and $\deg v_1 + \deg v_2 \ge n\in\mathbb{N}$. Then $G$ is Hamiltonian iff $G' = G + v_1 v_2$ is Hamiltonian.
Proof Assume $G'$ is Hamiltonian but not $G$. Therefore, by definition, there exists a cycle $(p_1,\ldots,p_n)$ in $G$ connecting $v_1$ (at $p_1$) to $v_2$ (at $p_n$) visiting all of $G$'s vertices. If $p_k\bowtie p_1$ then $p_{k-1} \not\bowtie p_n$, since $(p_1,p_k,p_{k+1},\ldots,p_n,p_{k-1},p_{k-2},\ldots,p_1)$ is a Hamiltonian cycle of $G$. As such, $\deg p_n \le n - (1 + \deg p_1)$, a contradiction.
