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.

Treść twierdzenia

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

$\deg(v)+\deg(u)\geqslant n$

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

Wersja twierdzenia z drogą Hamiltona

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

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

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

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 te, które mają najmniejszą liczbę wierzchołków, a spośród nich (grafów) taki, dla którego wartość $|E(G)|$ jest maksymalna. Jest to podgraf pełnego grafu hamiltonowskiego $K_{n}.$ Dodanie do $G$ krawędzi z grafu $K_{n}$ daje w wyniku graf, który nadal spełnia założenia twierdzenia i który ma więcej niż $|E(G)|$ 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, $v_{1},v_{2},\dots ,v_{n}.$ Ponieważ $G$ nie ma cyklu Hamiltona, to nie istnieje krawędź łącząca $v_{1}\ i\ v_{n}.$ Z kolei z założenia wiemy, że:

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

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

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

i

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

wtedy:

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

Ponieważ:

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

i zbiór

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

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

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

jest cyklem Hamilotona w grafie $G,$ sprzeczność. QED.

Zobacz też

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

Bibliografia

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