Twierdzenie Ore
Z Wikipedii
Twierdzenie Ore pozwalajace stwierdzić, czy graf jest hamiltonowski. Zostało sformułowane w roku 1961 przez norweskiego matematyka Øystein Ore.
[edytuj] Treść twierdzenia
Jeżeli w grafie G o n wierzchołkach, 
zachodzi następująca nierówność:
dla każdej pary nie połączonych bezpośrednio krawędzią wierzchołków u i v (tj. takich, że 
), to graf G jest hamiltonowski.
[edytuj] Dowód twierdzenia
Dowód nie wprost. Przypuśćmy, że twierdzenie jest fałszywe, czyli dla pewnej liczby n istnieje kontrprzykład G - graf, który spełnia założenie twierdzenia, ale nie jest Hamiltonowski. Spośród wszystkich takich grafów rozpatrzmy ten, który ma najmnieszą liczbę wierzchołków, a spośród nich taki, dla którego wartość 
jest maksymalna. Jest to podgraf pełnego grafu hamiltonowskiego Kn. Dodanie do G krawędzi z grafu Kn daje w wyniku graf, który nadal spełnia założenia twierdzenie i który ma więcej niż krawędzi, a więc ze względu na wybór grafu G tak powstały graf będzie miał cykl Hamiltona. To znaczy, że G musi mieć (przynajmniej) drogę Hamiltona, określoną przez pewien ciąg wierzchołków, 
. Ponieważ G nie ma cyklu Hamiltona, to nie istnieje krawędź łącząca 
. Z kolei z założenia wiemy, że:
Można teraz zdefiniować podzbiory zbioru 
takie, że:
i
wtedy:
i 
.
Ponieważ:
i zbiór
ma co najwyżej n-1 elementów, a więc zbiór 
musi być niepusty. Istnieje więc liczba i, dla której istnieją krawędzie 
. Wtedy droga:
jest cyklem Hamilotona w grafie G, sprzeczność. QED
