Twierdzenie o czterech barwach

Twierdzenie o czterech barwach

Twierdzenie o czterech barwach stwierdza, że dla każdego skończonego grafu planarnego istnieje funkcja kolorująca, która przypisuje wierzchołkom jedną z czterech barw tak, aby żadne dwa sąsiadujące wierzchołki nie miały tej samej barwy. Jest to jeden z najbardziej znanych problemów matematycznych.

Wersja dla mapy politycznej

Alternatywne sformułowanie twierdzenia mówi, że dowolną mapę polityczną można zabarwić czterema kolorami, zapewniając, że sąsiadujące kraje mają różne kolory. W tym przypadku „kraje” można zinterpretować jako wierzchołki w grafie, co ilustruje równoważność obu sformułowań.

Historia twierdzenia

Hipotezę o czterech barwach po raz pierwszy postawił August Ferdinand Möbius w 1840 roku, a Francis Guthrie niezależnie w 1852 roku. Pełny dowód został zaprezentowany dopiero w 1976 roku przez Wolfganga Hakena i Kennetha Appela, jednak był on kontrowersyjny, ponieważ wymagał sprawdzenia 1936 przypadków za pomocą komputerów. Wątpliwości co do poprawności dowodu zostały usunięte w 1994 roku dzięki jego modyfikacji, a w 2004 roku potwierdzono go przy użyciu komputerowego asystenta. Do tej pory nikt nie zdołał udowodnić tego twierdzenia bez wsparcia technologii.

Uogólnienia na inne powierzchnie

Twierdzenie o czterech barwach ma uogólnienia dla grafów na powierzchniach topologicznych, które nie są homeomorficzne ze sferą lub płaszczyzną. Dla tych powierzchni liczba kolorów potrzebnych do zabarwienia mapy politycznej odpowiada maksymalnej liczbie krajów, które graniczą ze sobą. Na przykład na torusie liczba ta wynosi 7, co oznacza, że matematycy musieliby dowodzić „twierdzenia o siedmiu barwach”.

Dla sfery i płaszczyzny również istnieje potwierdzenie uogólnionego twierdzenia, ponieważ maksymalna liczba krajów graniczących ze sobą wynosi tam 4. Uogólnione twierdzenie dla powierzchni innych niż sfera i płaszczyzna zostało udowodnione wcześniej niż twierdzenie o czterech barwach, co stanowiło ważny krok w tej dziedzinie matematyki.