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)|⩾3,$

oraz jeśli

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

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

to

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