Twierdzenie Orego

Twierdzenie Orego – twierdzenie podające warunek wystarczający na to, aby graf miał cykl Hamiltona. Zostało ono sformułowane w roku 1961 przez norweskiego matematyka Øysteina Orego.

Jeżeli w grafie prostym ${\displaystyle G}$ o n wierzchołkach, ${\displaystyle n>2}$ zachodzi następująca nierówność:

${\displaystyle \deg(v)+\deg(u)\geqslant n}$

dla każdej pary niepołączonych bezpośrednio krawędzią wierzchołków ${\displaystyle u}$ i ${\displaystyle v}$ (tj. takich, że ${\displaystyle \{v,u\}\notin E(G)}$), to graf ${\displaystyle G}$ posiada cykl Hamiltona.

Jeżeli w grafie prostym ${\displaystyle G}$ o n wierzchołkach, ${\displaystyle n>2}$ zachodzi następująca nierówność:

${\displaystyle \deg(v)+\deg(u)\geqslant n-1}$

dla każdej pary niepołączonych bezpośrednio krawędzią wierzchołków ${\displaystyle u}$ i ${\displaystyle v}$ (tj. takich, że ${\displaystyle \{v,u\}\notin E(G)}$), to graf ${\displaystyle G}$ posiada drogę Hamiltona.

Dowód nie wprost. Przypuśćmy, że twierdzenie jest fałszywe, czyli dla pewnej liczby ${\displaystyle n}$ istnieje kontrprzykład ${\displaystyle G}$ – graf, który spełnia założenie twierdzenia, ale nie jest Hamiltonowski. Spośród wszystkich takich grafów rozpatrzmy te, które mają najmniejszą liczbę wierzchołków, a spośród nich (grafów) taki, dla którego wartość ${\displaystyle |E(G)|}$ jest maksymalna. Jest to podgraf pełnego grafu hamiltonowskiego ${\displaystyle K_{n}.}$ Dodanie do ${\displaystyle G}$ krawędzi z grafu ${\displaystyle K_{n}}$ daje w wyniku graf, który nadal spełnia założenia twierdzenia i który ma więcej niż ${\displaystyle |E(G)|}$ krawędzi, a więc ze względu na wybór grafu ${\displaystyle G}$ tak powstały graf będzie miał cykl Hamiltona. To znaczy, że ${\displaystyle G}$ musi mieć (przynajmniej) drogę Hamiltona, określoną przez pewien ciąg wierzchołków, ${\displaystyle v_{1},v_{2},\dots ,v_{n}.}$ Ponieważ ${\displaystyle G}$ nie ma cyklu Hamiltona, to nie istnieje krawędź łącząca ${\displaystyle v_{1}\ i\ v_{n}.}$ Z kolei z założenia wiemy, że:

${\displaystyle \deg(v_{1})\ +\deg(v_{n})\geqslant n.}$

Można teraz zdefiniować podzbiory zbioru ${\displaystyle \{2,3,\dots ,n\}}$ takie, że:

${\displaystyle S_{1}\ =\ \{i:\ \{v_{1},v_{i}\}\in E(G)\}}$

i

${\displaystyle S_{n}\ =\{i:\{v_{i-1},v_{n}\}\in E(G)\},}$

wtedy:

${\displaystyle |S_{1}|\ =\deg(v_{1})}$ i ${\displaystyle |S_{n}|\ =\deg(v_{n}).}$

Ponieważ:

${\displaystyle |S_{1}|+|S_{n}|\geqslant n}$

i zbiór

${\displaystyle S_{1}\cup S_{n}}$

ma co najwyżej ${\displaystyle n-1}$ elementów, a więc zbiór ${\displaystyle S_{1}\cap S_{n}}$ musi być niepusty. Istnieje więc liczba ${\displaystyle i,}$ dla której istnieją krawędzie ${\displaystyle \{v_{1},v_{i}\}\ i\ \{v_{i-1},v_{n}\}.}$ Wtedy droga:

${\displaystyle v_{1},\dots ,v_{i-1},v_{n},\dots ,v_{i},v_{1}}$

jest cyklem Hamilotona w grafie ${\displaystyle G,}$ sprzeczność. QED.

• twierdzenie Diraca
• twierdzenie o liczbie krawędzi (graf hamiltonowski)
• twierdzenie Bondy’ego-Chvátala

• Robin James Wilson, Marek Kubale: Wprowadzenie do teorii grafów. Warszawa: Państwowe Wydawnictwo Naukowe, 1985, s. 53. ISBN 83-01-05247-3.