Tekst źródłowy strony Twierdzenie Bondy’ego-Chvátala

'''Twierdzenie Bondy’ego-Chvátala''' – twierdzenie pozwalające stwierdzić, czy [[graf (matematyka)|graf]] jest [[graf hamiltonowski|hamiltonowski]].

== Treść twierdzenia ==
Niech <math>G</math> będzie grafem o <math>n</math> wierzchołkach, a <math>C(G)</math> oznacza jego [[Graf (matematyka)|nadgraf]] zbudowany według reguły mówiącej, że dla każdej pary <math>\{v,u\}</math> <strong>niepołączonych</strong> bezpośrednio krawędzią wierzchołków takich, że:
: <math>\deg(v)+\deg(u)\geqslant n</math>

należy dodać krawędź <math>\{v,u\}.</math> Graf <math>G</math> jest hamiltonowski wtedy, i tylko wtedy, gdy <math>C(G)</math> jest hamiltonowski.

== Zobacz też ==
* [[twierdzenie Diraca]]
* [[twierdzenie Orego]]
* [[twierdzenie o liczbie krawędzi (graf hamiltonowski)]]

== Bibliografia ==
* {{Cytuj książkę |nazwisko=Gross |imię=Jonathan David |nazwisko2=Yellen |imię2=Jay |tytuł=Handbook of Graph Theory |wydawca=CRC Press |isbn=1-58488-090-2 |strony=801}}
{{Teoria grafów}}

[[Kategoria:Twierdzenia teorii grafów|Bondy’ego-Chvátala]]