Bondy and Chvátal theorem

Bondy and Chvátal’s theorem.
Let G be a graph of order n3 and suppose that u and v are distinct non adjacent verticesMathworldPlanetmath such that deg(u)+deg(v)n.

Then G is Hamiltonian if and only if G+uv is Hamiltonian.

Title Bondy and Chvátal theorem
Canonical name BondyAndChvatalTheorem
Date of creation 2013-03-22 11:52:57
Last modified on 2013-03-22 11:52:57
Owner drini (3)
Last modified by drini (3)
Numerical id 9
Author drini (3)
Entry type Theorem
Classification msc 05C45
Classification msc 81P99
Classification msc 81S30
Classification msc 81S99
Classification msc 81-00
Classification msc 81S05
Classification msc 81P15
Related topic HamiltonianGraph
Related topic OresTheorem