Twierdzenie Bondy’ego-Chvátala – twierdzenie pozwalające stwierdzić, czy graf jest hamiltonowski.
Treść twierdzenia Niech będzie grafem o wierzchołkach, a oznacza jego nadgraf zbudowany według reguły mówiącej, że dla każdej pary niepołączonych bezpośrednio krawędzią wierzchołków takich, że:
należy dodać krawędź Graf jest hamiltonowski wtedy, i tylko wtedy, gdy jest hamiltonowski.
Zobacz też twierdzenie Diraca twierdzenie Orego twierdzenie o liczbie krawędzi (graf hamiltonowski)
Bibliografia
Bondy’ego-Chvátala