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:

$\mathrm{deg}(v)+\mathrm{deg}(u)⩾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

• Szablon:Cytuj książkę