Twierdzenie o czterech kolorach to jeden z najsłynniejszych problemów matematycznych, zwany też zagadnieniem czterech barw. Twierdzenie to głosi, że dla każdego skończonego graf planarnego możliwe jest przypisanie każdemu z jego wierzchołków jednej z czterech liczb 1, 2, 3 i 4 w taki sposób, aby żadne sąsiednie wierzchołki nie miały przyporządkowanej tej samej liczby.
Twierdzenie_o_czterech_kolorach -
Sformułowanie równoważne (mniej ścisłe matematycznie, lecz bardziej przemawiające do wyobraźni): dowolną mapę polityczną na płaszczyźnie lub sferze można zabarwić czterema kolorami tak, aby każde dwa kraje mające wspólną granicę (a nie tylko wspólny wierzchołek) miały inne kolory (zakładamy, że wszystkie państwa są spójne terytorialnie).
Równoważność tych dwóch sformułowań łatwo zauważyć wyróżniając w każdym "kraju" "stolicę" i prowadząc drogi pomiędzy stolicami każdych dwóch sąsiednich krajów. Przechodzimy wówczas z mapy politycznej do grafu opisanego w pierwszym z powyższych sformułowań twierdzenia. Analogicznie można przejść w przeciwną stronę.

Próby udowodnienia

Dla pięciu barw dowód był stosunkowo prosty, jednakże twierdzenie o czterech barwach długo opierało się próbom udowodnienia, aż w końcu udało się to w 1976 roku. Dowód wszakże jest bardzo "brzydki", wymagał sprawdzenia 1936 przypadków szczególnych przy pomocy komputera. Pojawiały się nawet wątpliwości, czy dowód jest poprawny.
Wątpliwości te usunięto za pomocą jego modyfikacji w 1994, a w 2004 udało się dokonać sprawdzenia poprawności przy użyciu komputerowego asystenta. Nikt dotąd nie udowodnił twierdzenia o czterech barwach bez komputerowego wspomagania, choć wymyślono pewne uproszczenia oryginalnego dowodu. Przypadek ten stał się okazją do dyskusji na temat dopuszczalnych metod dowodowych w matematyce.

Uogólnienia na przypadek innych powierzchni

Istnieje uogólnienie twierdzenia o czterech barwach także dla grafów rozpiętych na powierzchniach topologicznych, które nie są homeomorficzne ze sferą lub płaszczyzną: dla każdej powierzchni liczba kolorów potrzebnych do zabarwienia dowolnej narysowanej na niej mapy politycznej tak, aby dwa sąsiednie kraje nie miały tej samej barwy, jest równa maksymalnej liczbie krajów na tej powierzchni, z których każdy dotyka każdego innego.
Na różnych powierzchniach liczba ta może być różna, na przykład na torusie (powierzchnia dętki) liczba ta wynosi 7 - matematycy żyjący na powierzchni takiej dętki uznaliby zapewne za ważniejsze dowodzenie "twierdzenia o siedmiu barwach".
Dla sfery i płaszczyzny uogólnione twierdzenie też jest prawdziwe, gdyż maksymalna liczba krajów, z których każdy dotyka każdego, jest na nich równa 4 (jeden kraj w środku i trzy dookoła).
To uogólnione twierdzenie dla wszelkich powierzchni poza sferą i płaszczyzną zostało udowodnione jeszcze wcześniej niż twierdzenie o czterech barwach. Pokonanie twierdzenia o czterech barwach uzupełniło więc dowód dla ostatnich dwóch szczególnych przypadków.

Referencje

Oryginalny dowód twierdzenia o czterech barwach: K. Appel and W. Haken. Every planar map is four colorable. Bulletin of the American Mathematical Society, wol. 82, 1976 str. 711-712.
Modyfikacja, która usunęła wątpliwości co do dowodu: N. Robertson, D. Sanders, P. Seymour, R. Thomas The Four Colour Theorem Preprint, luty 1994.
Doniesienie o sprawdzeniu poprawności dowodu za pomocą komputerowego asystenta Coq: http://www.maa.org/devlin/devlin_01_05.html
Publikacja wraz ze zdjęciami jest udostępniona w Encyklopedii "Zgapedia" części portalu zgapa.pl. Treść objęta jest licencją GNU FDL Wolnej Dokumentacji w wersji 1.3 lub dowolnej pózniejszej opublikowanej przez Free Software Foundation i została ona opracowana na podstawie Wikipedii, tutaj możesz znaleźć artykuł źródłowy oraz autorów. Warunki użytkowania Encyklopedii znajdziesz na tej stronie.