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

${\displaystyle |V(G)|\geqslant 3,}$

oraz jeśli

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

dla każdego wierzchołka w ${\displaystyle G,}$ to jest on hamiltonowski.

Dowód twierdzenia

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

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

to

${\displaystyle \deg(v)+\deg(u)\geqslant n}$

dla każdego wierzchołka ${\displaystyle v}$ i ${\displaystyle u}$ niezależnie od tego, czy są połączone krawędzią, czy nie, a więc ${\displaystyle 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)

Przypisy