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ż

Bibliografia

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