Inny, ciekawy problem można przedstawić na przykadzie firmy rozwożącej przesyłki. Dotyczy on pracy kuriera mającego rozwieść przesyłki do odbiorców, w ten sposób by odwiedzić każdego klienta jedynie raz, a na końcu wrócić do siedziby firmy. Załóżmy, że na przesyłki czeka następujący zbiór osób: Henryk, Elżbieta, Maciej, Jan, Ula, Izabela, Gabriela, oraz Maria. Niestety, jak widać z rysunku, nie ma połączeń umożliwiających przejazd między dowolnymi dwoma klientami.
Zachodzi pytanie, czy kurier mimo to jest w stanie wykonać swoje zadanie. Jeśli prześledzimy warunki nałożone na trasę swojej wędrówki okaże się, że szukamy tzw. cyklu Hamiltona.
Cykl Hamiltona to cykl przechodzący przez wszystkie wierzchołki grafu (czyli marszruta zamknięta odwiedzająca każdy wierzchołek dokładnie raz).
Graf hamiltonowski to graf posiadający cykl Hamiltona.
Ścieżka Hamiltona to ścieżka przechodząca przez wszystkie wierzchołki, każdy odwiedzając jedynie jeden raz.
W odróżnieniu od grafów eulerowskich, grafy hamiltonowskie nie posiadają prostej i szybkiej w użyciu charakteryzacji. Nie znana jest żadna metoda, pozwalająca szybko (tzn. w czasie wielomianowym) stwierdzić czy dany graf jest hamiltonowski. Są natomiast znane pewne warunki wystarczające na to, by graf był hamiltonowski. Jednym z ciekawszych takich warunków wystarczających jest warunek wykorzystujący jedynie stopnie wierzchołków. Przedstawiony jest w postaci następującego twierdzenia.
Twierdzenie 13.4 [Ore 1960]
Jeśli w grafie prostym \( \mathbf{G}=( V,E ) \) o co najmniej \( 3 \) wierzchołkach dowolne dwa niesąsiednie wierzchołki \( v \) i \( w \) spełniają \( \deg{v}+\deg{w}\geq \vert V \vert \), to graf \( \mathbf{G} \) jest hamiltonowski.
Dowód
Dla dowodu niewprost załóżmy, że pewien niehamiltonowski graf \( \mathbf{G} \) o \( n \) wierzchołkach spełnia
(*) \( \deg{v}+\deg{w}\geq n \), dla niesąsiednich wierzchołków \( v,w \).
Dodawanie krawędzi do \( \mathbf{G} \) nie psuje warunku (*), więc do grafu \( \mathbf{G} \) można dokładać krawędzie tak długo, jak długo jest on niehamiltonowski. Możemy więc dodatkowo założyć, że \( \mathbf{G} \) ma tę własność, że po dodaniu jakiejkolwiek krawędzi otrzymamy już cykl Hamiltona. Tak więc w \( \mathbf{G} \) musi istnieć ścieżka Hamiltona \( v_0\to v_1\to\ldots\to v_{n-1}\to v_n \).
Wierzchołek \( v_0 \) ma, poza wierzchołkiem \( v_1 \), dodatkowo \( \deg{v_0}-1 \) sąsiadów. Oznaczmy ich przez \( v_{i_1},\ldots,v_{i_{\deg{v_0}-1}} \). Z kolei, na mocy (*), wierzchołek \( v_n \) w zbiorze \( \lbrace v_2,\ldots,v_{n-2} \rbrace \) ma \( \deg{v_n}-1> (n-3)-(\deg{v_0}-1) \) sąsiadów. To gwarantuje, że \( v_n \) jest sąsiadem któregoś z \( \deg{v_0}-1 \) wierzchołków \( v_{i_1-1},\ldots,v_{i_{\deg{v_1}-1}-1} \). Istnieje więc takie miejsce \( j \) w ścieżce \( v_0\to v_1\to\ldots\to v_{n-1}\to v_n \), że \( v_1 \) jest incydentny z \( v_j \), zaś \( v_n \) z \( v_{j-1} \).
Tak więc cykl \( v_1\to v_j\to v_{j+1}\to\ldots\to v_n\to v_{j-1}\to v_{j-2}\to \ldots\to v_1 \) jest cyklem Hamiltona w grafie \( \mathbf{G} \), co w konsekwencji daje sprzeczność z faktem, że \( \mathbf{G} \) miał nie być hamiltonowski.
Twierdzenie Ore'a jest uogólnieniem silniejszego warunku znalezionego parę lat wcześniej przez Dirac'a.
Wniosek 13.5 [G. A. Dirac 1952]
Graf prosty \( \mathbf{G} =( V,E ) \), w którym każdy wierzchołek ma stopień co najmniej \( \vert V \vert/2 \) jest hamiltonowski.
Wróćmy teraz do przykładu o kurierze. Licząc stopnie wierzchołków w grafie z rysunku i używając Twierdzenia Ore'a możemy stwierdzić, że graf ten ma cykl Hamiltona. Tak więc kurier, nie bojąc się utraty pracy, może spokojnie spełnić swoje zadanie.