## Proof of Bondy and Chvátal Theorem

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

-

## 2 Answers

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 2010 at 6:06

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 28, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9357756972312927, "perplexity_flag": "head"}