Twierdzenie o liczbie krawędzi (graf hamiltonowski)

Twierdzenie o liczbie krawędzi pozwala stwierdzić, czy graf jest hamiltonowski.

Treść twierdzenia

Jeśli graf prosty o $n$ wierzchołkach ma co najmniej

${\frac {1}{2}}\cdot (n-1)(n-2)+2$

krawędzi, to jest hamiltonowski.

Dowód twierdzenia

Dla dowolnego grafu prostego $G$ załóżmy, że zachodzi

$|E(G)|\geqslant {\frac {1}{2}}\cdot (n-1)(n-2)+2={n-1 \choose 2}+2$

i weźmy wierzchołki $v$ i $u$ takie, że:

$\{v,u\}\notin E(G).$

Niech $H$ będzie grafem $G,$ z którego usunięto wierzchołki $v$ i $u$ oraz kończące się w nich krawędzie. Ponieważ:

$\{v,u\}\notin E(G),$

więc usunęliśmy $\deg(v)+\deg(u)$ krawędzi i dwa wierzchołki. $H$ jest podgrafem grafu $K_{n-2},$ a więc:

${n-2 \choose 2}=|E(K_{n-2})|\geqslant |E(H)|\geqslant {n-1 \choose 2}+2-\deg(v)-\deg(u),$

z czego wynika, że:

$\deg(v)+\deg(u)\geqslant {n-1 \choose 2}-{n-2 \choose 2}+2={\frac {1}{2}}(n-2)\cdot 2+2=n,$

a więc $G$ spełnia założenia twierdzenia Orego.

Zobacz też

• twierdzenie Bondy’ego-Chvátala
• twierdzenie Diraca (1952)
• twierdzenie Orego