Jednym z najbardziej znanych twierdzeń teorii grafów jest tzw. twierdzenie o czterech barwach. Jego dowód jest jednak na tyle skomplikowany, że matematycy musieli zaprząc do pomocy komputery aby finalnie to twierdzenie udowodnić. Nieco słabszym wynikiem jest twierdzenie o pięciu barwach, którego dowód prezentujemy w tym wpisie.
Problemy związane z kolorowaniem grafów mogą wydawać się jedynie matematyczną ciekawostką. Jednak wbrew pozorom mają nietrywialne zastosowania.
Początki tego typu zagadnień sięgają XIX wieku, gdy niejaki Francis Guthrie kolorował mapę Wielkiej Brytanii i zauważył, że potrzeba jedynie czterech barw aby dwa dowolne hrabstwa mąjące wspólną granicę (nie tylko wierzchołek) miały różne kolory. Doprowadziło to do sformułowania przez niego problemu, który obecnie znamy jako twierdzenie o czterech barwach. Twierdzenie to można często usłyszeć w formie popularnonaukowej mówiącej, że do pokolorowania każdej mapy wystarczą jedynie cztery kolory aby żadne dwa kraje mające wspólną granicę nie zostały pokolorowane tym samym kolorem.
Nie do końca jest to prawda. Pokazuje to, że trzeba uważać z formułowaniem matematycznych twierdzeń w luźniejszej, popularnonaukowej formie jak i że trzeba je traktować z lekkim przymrużeniem oka. Więcej szczegółów we wpisie dotyczącym twierdzenia o czterech barwach. Celem tego wpisu jest dowód nieco słabszego twierdzenia o pięciu barwach.
Twierdzenie to mówi, że wierzchołki każdego prostego grafu planarnego można pokolorować jedynie pięcioma barwami tak aby żadne dwa połączone krawędzią nie miały tego samego koloru. Treść tego twierdzenia jest analogiczna do jego odpowiednika dotyczącego czterech kolorów. Zalecamy przeczytanie wpisu o twierdzeniu o czterech barwach, gdyż stanowi naturalny wstęp oraz uzupełnienie tego wpisu.
Na początek trochę formalności.
Jeśli \(G=(V,E)\) jest grafem, to przez \(V\) oznaczamy zbiór jego wierzchołków, a przez \(E\) krawędzi. W dalszej części zakładamy, że \(G\) jest:
- prosty, tzn. każda krawędź łączy dwa różne wierzchołki (czyli nie ma pętli) oraz każdą parę wierzchołków może łączyć co najwyżej jedna krawędź;
- spójny, tzn. jest w jednym kawałku;
- planarny, tzn. można go narysować na płaszczyźnie bez przecinających się krawędzi.
Powyższy graf nie jest prosty, gdyż zawiera krawędź łączącą wierzchołek z samym sobą oraz jest para wierzchołków połączona więcej niż jedną krawędzią. Z kolei graf poniżej nie jest spójny, gdyż jest w dwóch kawałkach.
Tu natomiast mamy przykład grafu, który nie jest planarny. Nie da się go narysować na płaszczyźnie bez przecinających się krawędzi. Ma on 5 wierzchołków i każdy jest połączony z każdym. Dlatego nazywa się go grafem pełnym i oznacza \(K_5\).
Rzeczą, na którą należy zwrócić uwagę jest fakt, że konkretny graf planarny można często na wiele sposobów narysować na płaszczyźnie tak aby krawędzie się nie przecinały. Poniżej przykład dwu różnych realizacji na płaszczyźnie tego samego, z matematycznego punktu widzenia, grafu planarnego.
Założenie spójności nie jest konieczne aby udowodnić twierdzenie o pięciu barwach. W końcu każdy kawałek możemy kolorować oddzielnie, jednakże jest bardzo wygodne. Wystarczy je jedynie udowodnić, że jest prawdziwe dla grafów spójnych!
Każdy graf planarny możemy rysować bez przecinających się krawędzi nie tylko na płaszczyźnie, lecz również na sferze. Każdy taki graf podzieli sferę na oddzielne obszary zwane ścianami grafu.
Mówiąc bardziej precyzyjnie, ścianą grafu \(G\) nazywamy dowolny obszar sfery o tej własności, że dwa jego dowolne punkty możemy połączyć krzywą nieprzechodzącą przez żadną krawędź ani wierzchołek. Zatem to, który dokładnie obszar jest ścianą zależy od tego w jaki sposób graf \(G\) narysujemy na sferze. Nas jednak będzie interesowała jedynie ich liczba oraz to z jakimi krawędziami sąsiadują.
Dla grafów planarnych prawdziwy jest słynny wzór Eulera \[W-K+S=2,\]
gdzie \(W,\ K,\ S\) oznaczają odpowiednio liczbę wierzchołków, krawędzi oraz ścian. Pierwotnie wzór ten został udowodniony dla wielościanów takich jak sześcian, ostrosłupy czy graniastosłupy. Więcej o wzorze Eulera można znaleźć tutaj.
Każda krawędź znajduje się na brzegu jednej lub dwu ścian. Gdybyśmy na niej stanęli, to naszej lewej stronie mielibyśmy ścianę jak i po prawej znajdowałaby się (niekoniecznie inna) ściana.
Graf powyżej ma dwie ściany: zieloną (,,wewnętrzną”) oraz białą (,,zewnętrzną”). Krawędź \(e\) sąsiaduje jedynie ze ścianą zieloną. Zaś każda inna krawędź sąsiaduje z obiema. Liczbę krawędzi, z którymi sąsiaduje ściana \(f\) grafu \(G\) nazywamy jej stopniem i oznaczamy \(\deg{f}\). Przy czym, jeżeli krawędź \(e\) sąsiaduje tylko ze ścianą \(f\), to liczymy ją podwójnie. Ściana zielona grafu powyżej ma stopień równy 5, a biała 3. Zbiór ścian grafu \(G\) (a właściwie jego konkretnego rysunku) oznaczamy przez \(F\).
Zauważmy, że każda krawędź albo należy do dwu ścian albo ,,należy” podwójnie do jednej ściany. Wobec tego gdy zsumujemy stopnie wszystkich ścian, otrzymamy podwójną liczbę krawędzi. Tzn. \[\sum_{f\in F}\deg{f}=2K.\]
Podobnie jak o stopniu ściany, możemy mówić o stopniu wierzchołka \(v\). Jest to ilość krawędzi których jednym z końców jest \(v\). Oznaczamy go \(\deg{v}\), czyli analogicznie jak stopień ściany. Gdy graf zawiera pętle (stopień można zdefiniować dla dowolnego grafu), to każdą liczymy podwójnie. Nietrudno zauważyć, że \[\sum_{v\in V}=2K.\]
Jeżeli graf \(G\) ma co najmniej 3 wierzchołki, to ma co najmniej 2 krawędzie (bo zakładamy, że jest prosty, spójny i planarny). Ważną obserwacją jest to, że stopień każdej ściany to w takim przypadku co najmniej 3. Jedna lub dwie krawędzie (licząc w stosownych przypadkach niektóre z nich podwójnie) nie może stanowić brzegu ściany. Z tego wynika, że \[3S\leqslant 2K.\]
Podstawiając to do wzoru Eulera (pomnożonego przez 3) otrzymujemy \[0\leqslant 3W-3K+2K-6\] czyli \[K\leqslant 3W-6.\]
Korzystając z udowodnionej nierówności łatwo można pokazać, że graf \(K_5\) nie jest planarny, gdyż ma 5 wierzchołków oraz 10 krawędzi a \(3\cdot 5-6=9\lt 10\).
Kolejnym istotnym etapem dowodu jest pokazanie, że każdy prosty graf planarny ma przynajmniej jeden wierzchołek stopnia co najwyżej 5. W tym celu załóżmy, że jest to nieprawda, tzn. \(\deg{v}\gt 5\) dla każdego \(v\in V\). Wówczas \(6W\leqslant 2K\) bo suma stopni wierzchołków to \(2K\). Czyli \[3W\leqslant K\leqslant 3W-6.\] Otrzymana sprzeczność dowodzi, że \(\deg{v}\leqslant 5\) dla przynajmniej jednego wierzchołka.
Można to pokazać również w inny sposób, wykorzystując tzw. metodę rozładowywania. Ze względu na swą elegancję dowód ten jest warty przytoczenia.
Przypiszmy każdemu wierzchołkowi oraz każdej ścianie ładunek +6, natomiast każdej krawędzi -6. Ze wzoru Eulera wynika że, suma wszystkich ładunków jest równa 12. Teraz będziemy przesuwać ładunki, ale w taki sposób aby całkowity ładunek grafu się nie zmienił. Robimy to następująco:
- każdy wierzchołek oddaje +1 każdej krawędzi, której jest końcem;
- każda ściana oddaje równomiernie cały swój ładunek wszystkim krawędziom na swoim brzegu. Jeżeli krawędź sąsiaduje tylko z jedną ścianą, to jej udział jest podwójny.
Każda ściana zostaje w wyniku tego procesu całkowicie rozładowana. Natomiast ładunek wierzchołka \(v\), to \(6-\deg{v}\).
Ponieważ każda ściana sąsiaduje z co najmniej trzema krawędziami, to każda krawędź otrzyma od sąsiadujących ścian łączny ładunek co najwyżej +4. Dodatkowo otrzyma +2 od swoich końców. Zatem jej łączny ładunek nie może być dodatni! Aby suma ładunków była równa 12, to musi istnieć przynajmniej jeden wierzchołek o dodatnim ładunku czyli o stopniu mniejszym od 6.
Teraz możemy przejść do ostatniego etapu dowodu. Przeprowadzimy go indukcyjnie po liczbie wierzchołków. Jeżeli \(G\) ma co najwyżej 5 wierzchołków, to da się go pokolorować 5 kolorami. Załóżmy więc, że \(G=(V,E)\) ma \(n\) wierzchołków dla pewnego \(n>5\) oraz wszystkie grafy planarne o \(n-1\) wierzchołkach da się pokolorować co najwyżej 5 kolorami.
Graf \(G\) ma wierzchołek \(v\) stopnia co najwyżej 5. Usuńmy ten wierzchołek oraz wszystkie krawędzie z nim połączone. Otrzymany w ten sposób graf ma \(n-1\) wierzchołków, a więc na mocy założenie indukcyjnego jest 5-kolorowalny. Jeżeli \(\deg{v}\leqslant 4\), to bez problemu jesteśmy w stanie przypisać \(v\) kolor tak aby otrzymać poprawne kolorowanie grafu \(G\). Pozostaje więc do rozpatrzenia jedynie przypadek, gdy \(\deg{v}=5\) oraz wszystkie wierzchołki z nim połączone mają różne kolory.
Oznaczmy wierzchołki, z którymi \(v\) odpowiednio przez \(w_1,w_2,\ldots,w_5\). Ponieważ graf \(K_5\) nie jest planarny, to przynajmniej jedna para wierzchołków połączonych z \(v\) nie jest ze sobą połączona. Bez straty ogólności, możemy założyć, że są to wierzchołki \(w_1\) oraz \(w_2\).
Sklejamy teraz wierzchołki \(v, w_1, w_2\) oraz krawędzie \(\{v,w_1\}, \{v,w_2\}\) w nowy wierzchołek \(\tilde{v}\).
Zniknęły sklejone wierzchołki oraz krawędzie, a w ich miejsce pojawił się nowy wierzchołek \(\tilde{v}\). Zmieniły się również krawędzie połączone początkowo z jednym z tych wierzchołków. Jeżeli jednym z końców jakiejś niesklejanej krawędzi był któryś ze sklejonych wierzchołków, to został zastąpiony przez \(\tilde{v}\). Sklejanie fragmentów grafu w punkt może prowadzić do trzech problematycznych w naszym dowodzie rzeczy.
- Mogą pojawić się pętle.
Ponieważ z założenia \(w_1\) oraz \(w_2\) nie są ze sobą połączone, to ten problem nas nie dotyczy.
- Mogą pojawić się krawędzie wielokrotne.
Jeżeli co najmniej dwa spośród \(v,w_1,w_2\) są połączone z tym samym wierzchołkiem (różnym od \(v,w_1,w_2\) naturalnie), to po sklejeniu wierzchołek \(\tilde{v}\) będzie połączony z każdym z nich więcej niż jedną krawędzią. Usuwamy w tym przypadku krawędzie wielokrotne zostawiając tylko jedną. Z technicznego punktu widzenia nie ma dla nas znaczenia czy wierzchołki są połączone jedną czy większą ilością krawędzi. W przypadku kolorowania wierzchołków ważne jest jedynie, które wierzchołki są ze sobą połączone, a które nie. Jednak ponieważ rozpatrujemy grafy bez krawędzi wielokrotnych, to już się tego trzymamy.
- Otrzymany graf może nie być planarny.
Nietrudno jednak zauważyć, że ten problem nas również nie dotyczy. Jeżeli wierzchołek np. \(w_1\) jest połączony z np. wierzchołkiem \(z\neq v\), to łącząc krawędzie \(\{z,w_1\}\) oraz \(\{w_1,v\}\) w jedną łamaną (czyli nową krawędź) otrzymujemy na rysunku krawędź \(\{z,\tilde{v}\}\). Gdy natomiast \(w_1\) jest połączony tylko z \(v\), to sytuacja jest jeszcze prostsza. Analogicznie dla \(w_2\). Planarność \(G\) zostaje zachowana.
Otrzymaliśmy nowy graf \(\tilde{G}\) mający \(n-2\) wierzchołków i który jest również planarny i prosty. Na mocy założenia indukcyjnego jest 5-kolorowalny. Oznaczmy przez \(k\) kolor wierzchołka \(\tilde{v}\). Wykorzystując kolorowanie \(\tilde{G}\), pokolorujemy graf \(G\).
Każdemu wierzchołkowi \(z\in V\setminus \{v,w_1,w_2\}\) przypisujemy ten sam kolor jaki ma w grafie \(\tilde{G}\). Natomiast każdemu \(v,w_1\) oraz \(w_2\) przypisujemy kolor \(k\). Nie jest to jeszcze poprawne kolorowanie.
Zauważmy jednak, że żaden z wierzchołków połączonych z \(w_1\) oraz \(w_2\) nie może mieć koloru \(k\) bo w grafie \(\tilde{G}\) jest połączony z \(\tilde{v}\). Zostawiamy więc wierzchołkom \(w_1\) oraz \(w_2\) kolor \(k\). Wierzchołek \(v\) ma teraz dwa połączone z nim wierzchołki tego samego koloru, a połączony jest z pięcioma. Możemy go pokolorować brakującym kolorem. Twierdzenie o pięciu barwach zostało udowodnione.
Twierdzenia o czterech oraz pięciu barwach nie są jedynymi dotyczącymi kolorowania wierzchołków grafów. Tematyka ta jest niezwykle bogata. Wspomnimy jedynie o innym znanym wyniku jakim jest twierdzenie Brooksa.