Twierdzenie Diraca – twierdzenie pozwalające stwierdzić, czy graf jest hamiltonowski, zostało sformułowane w roku 1952. Nazwa pochodzi od Gabriela Diraca.
Treść twierdzenia Jeśli graf nie ma pętli, ani krawędzi wielokrotnych (jest grafem prostym) i
oraz jeśli
dla każdego wierzchołka w to jest on hamiltonowski.
Dowód twierdzenia Jeśli dla każdego wierzchołka
to
dla każdego wierzchołka i niezależnie od tego, czy są połączone krawędzią, czy nie, a więc spełnia założenia twierdzenia Ore, a więc jest hamiltonowski.
Zobacz też twierdzenie Bondy’ego-Chvátala twierdzenie Orego twierdzenie o liczbie krawędzi (graf hamiltonowski)
Przypisy
Diraca