# 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},\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\leq i\leq n$) then $x_{i-1}$ is not adjacent to $x_{n}$, for otherwise $(x_{1},x_{i},x_{i+1},\dots,x_{n},x_{i-1},x_{i-2},\dots,x_{1})$ is a Hamiltonian cycle of $G$. Thus $d(x_{n})\leq(n-1)-d(x_{1})$, that is $d(u)+d(v)\leq n-1$, a contradiction ∎

Title proof of Bondy and Chvátal theorem ProofOfBondyAndChvatalTheorem 2013-03-22 14:48:33 2013-03-22 14:48:33 taxipom (3607) taxipom (3607) 8 taxipom (3607) Proof msc 05C45