# 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 |