Te obrazki to grafy, czyli kropki (wierzchołki) połączone kreskami (krawędziami), a liczbę schodzących się w wierzchołku końców krawędzi nazywamy jego stopniem. Rozważamy tylko grafy spójne (w jednym kawałku) i o skończenie wielu wierzchołkach i krawędziach.

"Przechodząc" ołówkiem przez wierzchołek grafu, rysujemy zawsze dwie końcówki krawędzi - wchodzącą i wychodzącą. Aby zatem rysunek mógł powstać jednym pociągnięciem ołówka, w każdym wierzchołku liczba końców krawędzi musi być parzysta z wyjątkiem być może dwóch wierzchołków: początkowego i końcowego. Jeśli dodatkowo chcemy wrócić do punktu wyjścia, wyjątków tych być nie może. Zamknięta koperta (Rys. 1 (b)) ma cztery wierzchołki stopnia trzy, więc nie da się jej narysować jednym pociągnięciem ołówka.

Grafy, które da się w opisany sposób narysować, nazywamy grafami Eulera, a ślad ołówka odpowiednio drogą (jeśli końce są różne) lub cyklem Eulera (jeśli końce się pokrywają). Okazuje się, że sformułowany powyżej warunek konieczny jest również dostateczny i zachodzi następujące twierdzenie.

Warto porównać to twierdzenie z opisanymi w poprzednim deltoidzie czarno-białymi mapami.

Analogicznie graf skierowany (ze strzałkami na krawędziach) ma cykl Eulera wtedy i tylko wtedy, gdy w każdym wierzchołku liczba krawędzi wychodzących równa jest liczbie krawędzi wchodzących.

A czy istnieje graf o dokładnie jednym wierzchołku stopnia nieparzystego?

***

Mamy sejf otwierany czterocyfrowym, nieznanym nam kodem. Sprawdzenie po kolei wszystkich kodów od 0000 do 9999 wymagałoby wciśnięcia 40000 cyfr. Jednak można mniej się namęczyć. Otóż drzwi otworzą się, gdy ostatnie cztery spośród wprowadzonych cyfr utworzą właściwy kod, więc na przykład wciśnięcie kolejno cyfr 1 , 2 , 3 , 4 , 5 sprawdza dwa kody: 1234 i 2345.

Pokażemy, że istnieje taki ciąg 10003 cyfr (zwany ciągiem de Bruijna), w którym każda czwórka kolejnych cyfr jest inna. Oznacza to, że wciśnięcie w tej właśnie kolejności 10003 przycisków pozwoli na sprawdzenie wszystkich 10000 potencjalnych kodów i otwarcie sejfu. Szybciej się nie da (chyba że zgadniemy kod)!

Rys. 2 Przykładowy wierzchołek i jego krawędzie

Rozważmy graf (Rys. 2), którego wierzchołkami są trójki cyfr od 000 do 999 (odpowiadają one ostatnim trzem naciśniętym przyciskom). Z każdego z nich wychodzi 10 skierowanych krawędzi, podpisanych cyframi od 0 do 9 (jest ich zatem i odpowiadają one kodom: trzy cyfry wierzchołka i właśnie naciskana czwarta cyfra z krawędzi). Każda krawędź prowadzi do wierzchołka odpowiadającego aktualnej trójce ostatnio naciśniętych cyfr. Wobec tego również do każdego wierzchołka wchodzi po 10 krawędzi.

Skoro w tym grafie liczba krawędzi wchodzących do każdego wierzchołka jest równa liczbie jego krawędzi wychodzących, to istnieje cykl Eulera. Rysując graf zgodnie z tym cyklem i notując wierzchołek początkowy oraz cyfry z kolejnych krawędzi, otrzymamy poszukiwany ciąg de Bruijna zawierający wszystkie kody.

Rys. 3

Prostszy wariant powyższego problemu ilustruje rysunek 3, który przedstawia graf i cykl Eulera dla sejfu z trzycyfrowym kodem złożonym z cyfr 0 i 1. Cykl ten daje ciąg de Bruijna 0111010001 i łatwo sprawdzić, że faktycznie każda trójka kolejnych zer i jedynek występuje w tym ciągu dokładnie jeden raz.