proof of Bondy and Chvátal theorem

Proof.

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

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∎