Twierdzenie Diraca
Z Wikipedii
Twierdzenie Gabriela Diraca pozwalające stwierdzić, czy graf jest hamiltonowski, zostało sformułowane w roku 1952.
[edytuj] Treść twierdzenia
Jeśli graf G nie ma pętli, ani krawędzi wielokrotnych (jest grafem prostym) i
oraz jeśli
dla każdego wierzchołka w G, to jest on hamiltonowski.
[edytuj] Dowód twierdzenia
Jeśli dla każdego wierzchołka v:
to
dla każdego wierzchołka v i u, niezależnie od tego czy są połączone krawędzią, czy nie, a więc G spełnia założenia twierdzenia Ore, a więc jest hamiltonowski.
