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.

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.