proof of Bondy and Chvátal theorem

Proof.

The sufficiency of the condition is obvious and we shall prove the necessity by contradiction.

Assume that $G+uv$ is Hamiltonian but $G$ is not. Then $G+uv$ has a Hamiltonian cycle containing the edge $uv$. Thus there exists a path $P=(x_1,\mathrm{\dots },x_n)$ in $G$ from $x_1=u$ to $x_n=v$ meeting all the vertices of $G$. If $x_i$ is adjacent to $x_1$ ($2\le i\le n$) then $x_{i-1}$ is not adjacent to $x_n$, for otherwise $(x_1,x_i,x_{i+1},\mathrm{\dots },x_n,x_{i-1},x_{i-2},\mathrm{\dots },x_1)$ is a Hamiltonian cycle of $G$. Thus $d(x_n)\le (n-1)-d(x_1)$, that is $d(u)+d(v)\le n-1$, a contradiction ∎

Title	proof of Bondy and Chvátal theorem
Canonical name	ProofOfBondyAndChvatalTheorem
Date of creation	2013-03-22 14:48:33
Last modified on	2013-03-22 14:48:33
Owner	taxipom (3607)
Last modified by	taxipom (3607)
Numerical id	8
Author	taxipom (3607)
Entry type	Proof
Classification	msc 05C45