Leonhard Euler stanął przed następującym problemem. W Królewcu (wówczas Konigsbergu) na rzece Pregole, na której są dwie wyspy wybudowano siedem mostów łączące wyspy ze sobą, oraz z oboma brzegami rzeki. Układ mostów został przedstawiony na rysunku:
Pytanie, jakie zostało postawione Eulerowi, to czy można tak ułożyć spacer po wszystkich mostach Królewca, by po każdym przejść tylko raz i wrócić do punktu startowego. Euler oczywiście odpowiedział na zadane mu pytanie. Postaramy się rozwiązać Zagadnienie Mostów Królewieckich. Zacznijmy od przedstawienia powyższego problemu w języku grafów. Niech każdy spójny kawałek lądu w Królewcu odpowiada wierzchołkowi. Otrzymamy w ten sposób dwa wierzchołki odpowiadające wyspom oraz dwa obu brzegom Pregoły. Most pomiędzy dwoma kawałkami lądu będziemy interpretować jako krawędź łączącą wierzchołki odpowiadające tym skrawkom lądu. W ten sposób otrzymamy następujący graf (nie będący grafem prostym):
Naszym celem jest skonstruowanie specjalnego cyklu w grafie z rysunku Mapa mostów w Królewcu.
Cykl Eulera to zamknięta marszruta przechodząca przez każdą krawędź grafu dokładnie raz.
Graf eulerowski to graf posiadający cykl Eulera.
Graf na rysunku Grafy eulerowskie posiada cykl Eulera \( x\to u\to z\to y \to u \to z\to y\to x \), zaś graf w części b. nie jest eulerowski, bo jeżeli wejdzie się do wierzchołka \( v \), to już nie będzie można z niego wyjść; jeśli zaś rozpoczęlibyśmy naszą marszrutę z wierzchołka \( v \) to nie będzie można doń powrócić.
Grafy eulerowskie posiadają ładną charakterystykę umożliwiającą prostą i szybką weryfikację omawianej własności.
Twierdzenie 13.1
Graf \( \mathbf{G}=( V,E ) \) jest eulerowski wtedy i tylko wtedy, gdy jest spójny i stopień każdego wierzchołka jest parzysty.
Dowód
Załóżmy najpierw, że \( \mathbf{G} \) jest eulerowski i niech \( E \) jakimś jego cyklem Eulera. Poruszając się po \( \mathbf{G} \) wzdłuż cyklu \( E \) zliczajmy stopniowo używane krawędzie incydentne do poszczególnych wierzchołków. Zawsze po wejściu i wyjściu z danego wierzchołka \( v \) liczba policzonych krawędzi incydentnych z \( v \) zwiększy się o \( 2 \). Tak więc, jeśli \( v \) nie jest początkiem cyklu, to zawsze będzie miał parzystą liczbę aktualnie policzonych krawędzi incydentnych. Początek cyklu zaś, dopóki nie przeszliśmy ostatnią krawędzią grafu (która oczywiście prowadzi do niego) będzie miał nieparzystą liczbę policzonych krawędzi. Po użyciu jednak tej ostatniej krawędzi okaże się, że i on ma parzysty stopień. Żadna krawędź nie zostanie pominięta, ani policzona wielokrotnie, bo przeczyłoby to eulerowskości cyklu \( E \) lub spójności grafu \( \mathbf{G} \).
Dla dowodu implikacji odwrotnej, pokażmy najpierw, że jeżeli w skończonym grafie \( \mathbf{G} \) dowolny wierzchołek ma parzysty stopień, to \( \mathbf{G} \) posiada cykl. Istnienie takiego cyklu pokażemy wskazując jego kolejne krawędzie. Zaczynamy od dowolnie wybranej krawędzi \( v_0 v_1 \). Następnie przechodzimy do jakiejkolwiek innej krawędzi wychodzącej z wierzchołka \( v_1 \). Załóżmy, że była to krawędź \( v_1 v_2 \). Wybieramy następnie dowolną różną od \( v_1 v_2 \) krawędź wychodzącą z \( v_2 \). Czynność tę powtarzamy tak długo, aż dojdziemy do jakiegoś wierzchołka \( v_i \), który został już wcześniej odwiedzony. W ten sposób otrzymamy cykl \( v_i\to v_{i+1}\to \ldots\to v_k\to v_i \). Jedynym problemem mógłby, w jakimś momencie, być brak możliwości kontynuowania marszu zanim dojdziemy do odwiedzonego wcześniej punktu \( v_i \). Sytuacja taka nie jest jednak możliwa, gdyż oznaczałoby to istnienie wierzchołka o incydentnego z jedną tylko krawędzią (wejściową), co stoi w sprzeczności z parzystością jego stopnia.
Teraz możemy przejść do dowodu Twierdzenia, który przeprowadzimy indukcyjnie ze względu na liczbę krawędzi w grafie \( \mathbf{G} \). Jak już zauważyliśmy powyżej, graf \( \mathbf{G} \) posiada jakiś cykl \( C \). Usuńmy z grafu \( \mathbf{G} \) krawędzie i wierzchołki cyklu \( C \) otrzymując w ten sposób mniejszy graf \( \mathbf{G}' \). Graf \( \mathbf{G}' \) może już nie być spójny, ale nadal będzie posiadał jedynie wierzchołki parzystego stopnia. Jeżeli \( \mathbf{G}' \) jest pusty, to cykl \( C \) jest cyklem Eulera, co kończyłoby dowód. W przeciwnym razie, w każdej spójnej składowej grafu \( \mathbf{G}' \) nie będącej punktem izolowanym, korzystając z założenia indukcyjnego, znajdujemy cykle Eulera \( E_1,\ldots E_l \). Ponieważ graf \( \mathbf{G} \) był spójny, to cykl \( C \) musi przechodzić przez jakiś wierzchołek każdego cyklu \( E_1,\ldots E_l \). Tak więc cykl Eulera dla grafu \( \mathbf{G} \) możemy wyznaczyć w ten sposób, że przechodząc przez cykl \( C \), za każdym razem gdy napotkamy nieodwiedzony jeszcze cykl \( E_i \), zbaczamy z cyklu \( C \) i przechodzimy w całości \( E_i \), a później kontynuujemy wędrówkę po cyklu \( C \). W konsekwencji przejdziemy po wszystkich krawędziach, każdą odwiedzając jedynie raz.
Bogatsi o nowo zdobytą wiedzę możemy już negatywnie odpowiedzieć na pytanie postawione Leonhardowi Euler'owi.
Analizując dowód Twierdzenia 13.1 dostajemy następujący wniosek.
Wniosek 13.2
Graf spójny jest eulerowski wtedy i tylko wtedy, gdy rodzinę jego krawędzi da się podzielić na rozłączne krawędziowo cykle.
Z grafami eulerowskimi ściśle związane są grafy, które można narysować bez odrywania ołówka i rysując każdą krawędź dokładnie raz.
Graf jednokreślny to graf posiadający marszrutę przechodzącą dokładnie raz przez każdą krawędź.
Wniosek 13.3
Graf \( \mathbf{G}=( V,E ) \) jest jednokreślny wtedy i tylko wtedy, gdy jest spójny i jego wszystkie, poza co najwyżej dwoma wierzchołkami, mają parzysty stopień.
Dowód
Jeśli \( \mathbf{G} \) jest jednokreślny, i marszruta przechodząca przez każda krawędź jest cyklem, to \( \mathbf{G} \) jest eulerowski i wobec Twierdzenia 13.1 ma jedynie wierzchołki o parzystym stopniu. Jeśli zaś marszruta ta nie jest cyklem, to oczywiście wszystkie wierzchołki poza początkowym i końcowym mają parzysty stopień.
Na odwrót, jeśli w grafie \( \mathbf{G} \) wszystkie wierzchołki mają parzysty stopień, to \( \mathbf{G} \) jest eulerowski, a zatem jednokreślny. Jeśli zaś \( \mathbf{G} \) ma wierzchołki o nieparzystym stopniu, to - wobec naszego założenia, może ich mieć dokładnie dwa, bo może mieć jedynie parzyście wiele wierzchołków o nieparzystym stopniu. Łącząc teraz te dwa wierzchołki nową krawędzią, dostajemy graf \( \mathbf{G'} \), w którym już wszystkie wierzchołki mają parzysty stopień. A zatem \( \mathbf{G'} \) posiada cykl Eulera \( E \). Cykl ten przechodzi oczywiście przez nowo dodana krawędź. Usuwając ją z cyklu \( E \) dostajemy marszrutę w grafie \( \mathbf{G} \), świadcząca o jego jednokreślności.