Deltoid

Kraje, stolice, granice...

Styczniowy deltoid poświęcony był dwubarwnym mapom...

Udowodniliśmy w nim

Twierdzenie 1. Mapę można pomalować dwoma kolorami wtedy i tylko wtedy, gdy każdy jej wierzchołek jest stopnia parzystego.

Przyjmujemy tę samą terminologię oraz założenia o mapach i ich kolorowaniach.

| n 1,k 3, — Rys. 3 $n 1,k 3,$ więc $Q$ ma kolor $1 | 3 2 1 mod 3$

Rys. 4 Dwoma kolorowymi bokami trójkąta zastępujemy pojedynczą krawędź drogi $|d$ (trzeci bok tego trójkąta)

Ograniczmy teraz nasze rozważania do map regularnych (definicja na marginesie). W każdym wierzchołku takiej mapy schodzą się trzy kraje, z pewnością więc dwie barwy nie wystarczą do pomalowania ich. Co więcej, jeśli jakiś kraj ma nieparzystą liczbę sąsiadów, to nie da się ich pokolorować dwiema barwami (Rys. 1). Dowodzi to jednej z implikacji w poniższym twierdzeniu.

Twierdzenie 2. Mapę regularną można pomalować trzema kolorami wtedy i tylko wtedy, gdy każdy jej kraj ma parzystą liczbę sąsiadów.

W dowodzie drugiej implikacji przyda się pojęcie mapy $M′$ dualnej do mapy $|M$ : jej wierzchołkami są stolice państw mapy $M,$ a jeśli dwa państwa sąsiadują, to w poprzek ich granicy rysujemy krawędź łączącą stolice (Rys. 2).

Dowód. Jeśli każdy kraj na mapie $M$ ma parzystą liczbę sąsiadów, to każdy wierzchołek mapy $|M′$ ma stopień parzysty. Na mocy twierdzenia 1 możemy więc mapę $M′$ pomalować na czarno-biało. Ponadto każdy jej kraj jest trójkątem, co wynika z regularności mapy $|M.$ Pomalujemy wierzchołki $|M′$ barwami 0, 1, 2.

Pokolorujmy dowolny wierzchołek $P$ barwą 0. Następnie każdy inny wierzchołek $Q$ połączmy z $|P$ dowolnym ciągiem różnych krawędzi i pomalujmy kolorem $n − k(mod 3),$ gdzie $n$ to liczba krawędzi wzdłuż tej drogi od $P$ do $|Q,$ które mają czarny trójkąt po lewej stronie, a $k$ - po prawej (Rys. 3). Aby zakończyć dowód, należy wykazać, że kolor wierzchołka $Q$ nie zależy od wyboru drogi.

Rozważmy dwie różne drogi $d$ i $′ |d$ i deformujmy $|d$ do $′ d ,$ "mijając" kolejne trójkąty jak na rysunku 4 Wówczas jedną krawędź wliczaną do $|n$ zastępujemy dwiema liczonymi do $k$ lub jedną z $k$ - dwiema z $|n.$ Ponieważ $2 ≡ −1$ oraz $|−2 ≡ 1(mod 3),$ taka zmiana nie wpływa na kolor wierzchołka $Q.$ Stąd faktycznie kolor ten nie zależy od wyboru drogi, a barwy sąsiednich wierzchołków (państw mapy $|M$ ) różnią się o 1.

****

Słynne twierdzenie orzeka, że każdą mapę da się pomalować najwyżej czterema barwami.
Dowodu (bardzo trudnego) nie przedstawimy, ale pokażemy równoważność pewnych warunków.

Twierdzenie 3. Mapę regularną można pomalować czterema kolorami wtedy i tylko wtedy, gdy jej krawędzie można pomalować trzema kolorami tak, by w każdym wierzchołku schodziły się krawędzie trzech różnych barw.

Dowód. Rozważmy mapę pomalowaną czterema kolorami: $|(0,0),(0,1),(1,0)$ , $|(1,1).$ Pokolorujmy każdą z krawędzi barwą odpowiadającą sumie graniczących wzdłuż niej państw, przy czym dodawanie wykonujemy po współrzędnych i modulo 2, np. $(1,0)+ (1,1) = (0,1).$ Są wówczas tylko trzy możliwe kolory krawędzi: $|(0, 1),(1,0),(1,1)$ - sumy sześciu możliwych par różnych barw krajów.

Zauważmy, że każda barwa zsumowana sama ze sobą daje $(0,0).$ Stąd suma kolorów trzech krawędzi w każdym z wierzchołków też równa jest $|(0,0),$ gdyż kolor każdego z państw jest w niej liczony dwukrotnie. Wobec tego dwie krawędzie jednego wierzchołka nie mogą mieć tego samego koloru, gdyż wówczas ich suma byłaby równa $|(0,0)$ i zmieniłaby się po dodaniu trzeciej (różnej od $(0,0)$ ). Uzyskaliśmy więc odpowiednie kolorowanie krawędzi.

Załóżmy teraz, że krawędzie mapy pokolorowano barwami $|(0,1),(1,0),(1,1)$ w sposób opisany w twierdzeniu. Pomalujmy dowolnie wybrany kraj $P$ kolorem $(0,0).$ Następnie każdy inny kraj $|Q$ połączmy z $|P$ dowolną drogą nieprzechodzącą przez wierzchołki mapy i pomalujmy kolorem równym sumie barw wszystkich przekraczanych po drodze granic. Aby zakończyć dowód, należy wykazać, że kolor państwa $Q$ nie zależy od wyboru drogi. Rozumowanie to, bazujące na deformowaniu drogi, przebiega analogicznie do dowodu twierdzenia 1 (tym razem każdy wierzchołek ma stopień 3 i suma kolorów dwóch jego krawędzi równa jest kolorowi trzeciej). Barwy sąsiednich krajów różnią się wówczas o barwę ich granicy.