Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 8 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.