# Bondy and Chvátal theorem

Bondy and Chvátal’s theorem.

Let $G$ be a graph of order $n\ge 3$ and suppose that $u$ and $v$ are distinct non adjacent vertices^{} such that $\mathrm{deg}(u)+\mathrm{deg}(v)\ge 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 |