Tekst źródłowy strony Twierdzenie o liczbie krawędzi (graf hamiltonowski)

{{dopracować|źródła=2014-01}}
'''Twierdzenie o liczbie krawędzi''' pozwala stwierdzić, czy [[graf (matematyka)|graf]] jest [[graf hamiltonowski|hamiltonowski]].

== Treść twierdzenia ==
Jeśli [[graf prosty]] o <math>n</math> [[Wierzchołek (teoria grafów)|wierzchołkach]] ma co najmniej
:<math>\frac{1}{2} \cdot (n-1)(n-2) + 2</math>

krawędzi, to jest hamiltonowski.

== Dowód twierdzenia ==
Dla dowolnego grafu prostego <math>G</math> załóżmy, że zachodzi
: <math>|E(G)|\geqslant \frac{1}{2}\cdot (n-1)(n-2) + 2 = {n-1 \choose 2} + 2</math>

i weźmy wierzchołki <math>v</math> i <math>u</math> takie, że:
: <math>\{v,u\}\notin E(G).</math>

Niech <math>H</math> będzie grafem <math>G,</math> z którego usunięto wierzchołki <math>v</math> i <math>u</math> oraz kończące się w nich krawędzie. Ponieważ:
: <math>\{ v,u\}\notin E(G),</math>

więc usunęliśmy <math>\deg(v) + \deg(u)</math> krawędzi i dwa wierzchołki. <math>H</math> jest [[podgraf]]em grafu <math>K_{n-2},</math> a więc:
: <math>{n-2 \choose 2} = |E(K_{n-2})|\geqslant |E(H)|\geqslant {n-1 \choose 2} + 2 - \deg(v) - \deg(u),</math>

z czego wynika, że:
: <math>\deg(v) + \deg(u)\geqslant {n-1 \choose 2} - {n-2 \choose 2} + 2 = \frac{1}{2}(n-2)\cdot 2 + 2 = n,</math>

a więc <math>G</math> spełnia założenia [[Twierdzenie Orego|twierdzenia Orego]].

== Zobacz też ==
* [[twierdzenie Bondy’ego-Chvátala]]
* [[twierdzenie Diraca]] ([[1952]])
* [[twierdzenie Orego]]

{{Teoria grafów}}

[[Kategoria:Twierdzenia teorii grafów|O liczbie krawędzi grafu hamiltonowskiego]]