Twierdzenie Diraca

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 $G$ nie ma pętli, ani krawędzi wielokrotnych (jest grafem prostym) i

$|V(G)|\geqslant 3,$

oraz jeśli

$\deg(v)\geqslant {\frac {|V(G)|}{2}}$

dla każdego wierzchołka w $G,$ to jest on hamiltonowski.

Dowód twierdzenia

Jeśli dla każdego wierzchołka $v{:}$

$\deg(v)\geqslant {\frac {n}{2}},$

to

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

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.

Zobacz też

• twierdzenie Bondy’ego-Chvátala
• twierdzenie Orego
• twierdzenie o liczbie krawędzi (graf hamiltonowski)