proof of Bondy and Chvátal theorem


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

Assume that G+uv is Hamiltonian but G is not. Then G+uv has a Hamiltonian cycleMathworldPlanetmath containing the edge uv. Thus there exists a path P=(x1,,xn) in G from x1=u to xn=v meeting all the vertices of G. If xi is adjacent to x1 (2in) then xi-1 is not adjacent to xn, for otherwise (x1,xi,xi+1,,xn,xi-1,xi-2,,x1) is a Hamiltonian cycle of G. Thus d(xn)(n-1)-d(x1), that is d(u)+d(v)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