Twierdzenie Bondy’ego-Chvátala

Twierdzenie Bondy’ego-Chvátala – twierdzenie pozwalające stwierdzić, czy graf jest hamiltonowski.

Treść twierdzenia

Niech $G$ będzie grafem o $n$ wierzchołkach, a $C(G)$ oznacza jego nadgraf zbudowany według reguły mówiącej, że dla każdej pary $\{v,u\}$ niepołączonych bezpośrednio krawędzią wierzchołków takich, że:

$\deg(v)+\deg(u)\geqslant n$

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

Zobacz też

• twierdzenie Diraca
• twierdzenie Orego
• twierdzenie o liczbie krawędzi (graf hamiltonowski)

Bibliografia

• Jonathan David Gross, Jay Yellen: Handbook of Graph Theory. CRC Press, s. 801. ISBN 1-58488-090-2.