# Proof of Bondy and Chvátal Theorem

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.

-
This is perfect. Thank you. –  LBushkin Jan 24 '10 at 6:06

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.

-