Jednym z najbardziej znanych wyników dotyczących teorii grafów jest słynne twierdzenie o czterech barwach z którego, jak się mówi, można wywnioskować, że kraje na każdej mapie można pokolorować korzystając jedynie z czterech kolorów. Twierdzenie to jest świetnym przykładem tego, że należy uważać formułując twierdzenia matematyczne w wersji popularnonaukowej, bo w rzeczywistości nie każdą mapę da się pokolorować jedynie czterema kolorami.
W 1852 roku Francis Guthrie kolorując mapę Wielkiej Brytanii zauważył, że wystarczą jedynie cztery kolory, aby każde dwa hrabstwa mąjące wspólną granicę (nie tylko wspólny wierzchołek) miały różne kolory. Nietrudno zauważyć, że trzy kolory nie wystarczą. Naturalnym jest więc pytanie czy cztery barwy wystarczą, aby pokolorować każdą mapę.
Problem był na tyle ciekawy, że zainteresowali się nim matematycy. Przez długi czas nikt nie był w stanie przedstawić dowodu. Pierwszym poważną próbę podjął Alfred Kempe. Jednak jego, opublikowany w 1879 roku, ,,dowód” zawierał błąd. Oryginalną pracę Kempego można znaleźć w tym miejscu.
Po 11 latach błąd w pracy Kempego znalazł Headwood. Wykorzystując idee Kempego udowodnił nieco słabsze twierdzenie o pięciu barwach. Dowód tego twierdzenia (nieoryginalny) można znaleźć tutaj.
Aby móc twierdzenie o czterech barwach udowodnić najpierw trzeba historyjkę o kolorowaniu map przetłumaczyć na precyzyjny język matematyki. Można to zrobić wykorzystując teorię grafów.
Intuicyjnie, graf jest zbiorem wierzchołków połączonych kreskami, które zwie się krawędziami.
Nas najbardziej będą interesowały grafy o skończonej liczbie wierzchołków i krawędzi oraz nie posiadające pętli (czyli krawędzi łączących wierzchołek z samym sobą). Ponadto zakładamy, że dowolną parę wierzchołków może łączyć co najwyżej jedna krawędź oraz każda krawędź łączy dwa różne wierzchołki. Takie grafy nazywamy prostymi. Jeżeli ponadto graf jest w jednym kawałku, to nazywamy go spójnym.
Mówiąc już bardziej ściśle, graf \(G\) mający \(n\) wierzchołków oraz \(m\) krawędzi to para uporządkowana \((V,E)\), gdzie:
- \(V=\{v_1, v_2,\ldots, v_n\}\) jest niepustym zbiorem wierzchołków,
- \(E=\{e_1, e_2,\ldots, e_m\}\) jest zbiorem krawędzi.
Przy czym \(e_i=\{x,y\}\), gdzie \(x,y\in V\) oraz \(x\neq y\) (bo zakładamy, że graf nie ma pętli).
Wiele obiektów spotykanych w prawdziwym życiu można utożsamiać z pewnym grafem. Przykładem są układy elektroniczne, które składają się z elementów połączonych np. przewodami. Wobec tego możemy je przedstawić w postaci grafu.
Z każdą mapą możemy stowarzyszyć pewien graf. Pokażemy to na przykładzie mapy przedstawiającej podział administracyjny Polski na województwa.
Każde województwo możemy utożsamiać z wierzchołkiem, natomiast krawędź oznacza, że dane dwa województwa mają wspólną granicę. W przypadku podziału administracyjnego Polski tak otrzymany graf może wyglądać np. tak:
Graf otrzymany z mapy Polski jest przykładem bardzo ważnej klasy grafów tzw. grafów planarnych, tj. takich, które można narysować na płaszczyźnie bez przecinających się krawędzi. Wiedza czy dany graf jest planarny może być przydatna w elektronice. Jeżeli dany układ elektroniczny ma zostać zmontowany na jakiejś powierzchni np. na tzw. płytce drukowanej (takiej jak poniżej), to jego poprawne działanie wymaga aby połączenia poszczególnych elementów się nie przecinały.
Przedstawiając elementy układu oraz to jak są połączone w postaci grafu możemy się dowiedzieć, że danego układu nie da się zmontować na płytce bo stosowny graf nie jest planarny i musimy wykorzystać trzy wymiary.
Matematycy już od bardzo dawna znają warunki pozwalające stwierdzić czy graf jest planarny czy nie. Proste kryterium podaje twierdzenie Kuratowskiego. Standardowym przykładem grafu nieplanarnego jest poniższy graf:
Składa się z pięciu wierzchołków i każda para różnych wierzchołków jest połączona krawędzią. Grafy o tej własności nazywamy pełnymi. Graf pełny o \(n\) wierzchołkach oznaczamy \(K_n\).
Innym przykładem jest poniższy graf \(K_{3,3}\).
Nietrudno zauważyć, że jego wierzchołki są podzielone na dwie grupy. Każdy górny wierzchołek jest połączony z każdym dolnym. Taki graf nazywamy pełnym dwudzielnym.
Należy zauważyć, że z samego faktu, iż rysunek grafu zawiera przecinające się krawędzie nie wynika, że nie jest on planarny. W definicji grafu interesuje nas jedynie które wierzchołki są połączone krawędziami. Rysunek danego grafu można na ogół wykonać na wiele różnych sposobów.
Kolorowanie grafu oznacza przypisanie kolorów jego wierzchołkom w taki sposób, aby żadne dwa połączone krawędzią nie miały takiego samego koloru. Najmniejszą możliwą liczbę kolorów jaką można pokolorować dany graf nazywamy jego liczbą chromatyczną. Twierdzenie o czterech barwach mówi więc, że liczba chromatyczna każdego prostego grafu planarnego jest równa co najwyżej 4.
Dlaczego więc, mimo iż samo twierdzenie o czterech barwach jest prawdziwe, to jednak nie każdą mapę można pokolorować używając jedynie czterech kolorów? Jest kilka problemów. Ci co bardziej spostrzegawczy zapewne zauważyli, że twierdzenie o czterech barwach mówi o grafach planarnych, a przecież Ziemia jest nieco zniekształconą sferą. Na sferze bez problemu da się narysować bez samoprzecięć każdy graf planarny. Jednak czy każdy graf, który można bez samoprzecięć narysować na sferze jest planarny nie jest już takie oczywiste na pierwszy rzut oka. Na szczęście na drugi rzut oka, pokazanie iż jest tak w istocie nie jest wcale trudne. Można się o tym łatwo przekonać wykorzystując tzw. rzut streograficzny.
Sferyczność Ziemi nie jest więc problemem. Spójrzmy jednak na poniższą mapę
Na niebiesko zaznaczono dwa jeziora. Z oczywistych powodów chcemy, aby wszystkie zbiorniki wodne miały ten sam kolor. Jednak nie tworzą one spójnej całości i w przypadku powyższej mapy możemy albo użyć pięciu kolorów albo oba jeziora pokolorować innymi kolorami.
Nie zapominajmy, że są również kraje, które nie są w jednym kawałku. Poszczególne kraje traktujemy jak jeden wierzchołek, dlatego graf otrzymany w przypadku kraju, który składa się z kilku terytoriów może nie być planarny.
Jeżeli pominąć morza i oceany, to mapę polityczną świata można pokolorować korzystając jedynie z czterech kolorów.
Twierdzenie o czterech barwach zostało udowodnione dopiero w XX wieku i to przy użyciu komputerów. Dokonali tego Kenneth Apple i Wolfgang Hapel. Więcej na temat historii samego dowodu oraz jego idei można poczytać tutaj.
Dowód twierdzenia o czterech barwach okazał się niezwykle trudny. Zadowoliwszy się nie czterema barwami a pięcioma barwami, otrzymamy wspomniane już twierdzenie o pięciu barwach (zaskakująca nazwa, nieprawdaż?), którego dowód jest znacznie łatwiejszy.