|
6
|
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. |
||
|
|
|
8
|
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. |
|||
|
|
3
|
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. |
|||
|
|
