Twierdzenie o liczbie krawędzi (graf hamiltonowski)

Szablon:Dopracować 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) | ⩾ \frac{1}{2} \cdot (n - 1) (n - 2) + 2 = (\binom{n - 1}{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:

(\binom{n - 2}{2}) = | E (K_{n - 2}) | ⩾ | E (H) | ⩾ (\binom{n - 1}{2}) + 2 - \deg (v) - \deg (u),

z czego wynika, że:

\deg (v) + \deg (u) ⩾ (\binom{n - 1}{2}) - (\binom{n - 2}{2}) + 2 = \frac{1}{2} (n - 2) \cdot 2 + 2 = n,

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