Most bebizonyítjuk a már említett ötszín tételt, amely
szerint: Öt színnel már bármilyen normál térkép jól színezhető a
gömbön. Megmutatjuk, hogy ezt az állítást elegendő olyan normál
térképekre bizonyítani, amelyeken minden ország elemi felület, és
minden csúcspontból pontosan háromfelé indul határvonal. Nevezzük
el az ilyen térképeket szabályosaknak!
I. Legyen normál térképünkön
L
egy nem elemi felületország, mint pl. a 7/a.
ábrán. Az
L
belsejében levő országcsoportokat kössük össze az
L
-et körülvevő határvonalhoz vezető útszakaszokkal
(szaggatott vonalak). Ezeket a szakaszokat bővítsük ki egy-egy
L
-ben fekvő országgá (7/b. ábra). Így
L
-ből elemi felület lesz. A felvett új
L
1
és
L
2
ország a többi ország között eredetileg fennálló
szomszédosságokat nem szüntette meg, ha tehát az így módosított
térkép
5 színnel jól színezhető, akkor az eredeti
is.
II. Ha van a normál térképen olyan
P
csúcspont, amelyből háromnál többfelé indul
határvonal (8/a. ábra),
akkor rajzoljunk köréje olyan kört, amelybe a
P
csúcsponton kívül más csúcspont nem esik, és amely
a
P
-ből induló határvonalakat csak egy-egy pontban
metszi (8/b. ábra). E kör belsejét csatoljuk az egyik
P
körüli országhoz (8/c. ábra). Ezzel
szomszédosságot nem szüntettünk meg, esetleg létrehoztunk. Ha tehát
az így módosított térkép
5 színnel jól színezhető, akkor az eredeti is. Ez
után a módosítás után előfordulhat, hogy egy új él egy országon
belül halad; ha pl. egy
L
ország a
P
pont körül többször is felbukkan (9/a. és 9/b.
ábra). Az ilyen él fölösleges, és ezért töröljük (9/c.
ábra).
Az I. és II. lépések ismételt alkalmazásával minden normál
térkép szabályossá alakítható, és – amint láttuk – az eredeti
normál térkép jó színezéséhez sem kell több szín, mint az I. és II.
lépések ismételt alkalmazásával nyert szabályos térkép jó
színezéséhez.
Megemlítjük, hogy ha a gömb egy szabályos térképén kettőnél
több ország van, akkor közöttük nincs olyan, amelynek határvonalán
csúcspont ne volna. Ekkor tehát minden határvonal élekből
összerakható. Az is igaz, hogy szabályos térképen nincs csupán egy
éllel határolt ország. Mindkét állítás belátását az olvasóra
bízzuk.
Ezek után azt fogjuk bizonyítani, hogy egy tetszőleges, a
gömböt befedő
T
szabályos térkép
5 színnel jól színezhető. Jelöljük
T
országainak számát
l
-lel, éleinek számát
é
-vel és csúcspontjainak számát
c
-vel!
T
minden országa elemi felület, tehát Euler tétele
szerint
Számoljuk össze a csúcspontok segítségével az éleket!
T
minden csúcspontjához
3 különböző él illeszkedik. Minden él pontosan két
csúcsponthoz illeszkedik, ti. a két végpontjához. Ezért igaz, hogy
Ha az Euler-egyenlőség mindkét oldalát
6-tal szorozzuk, és
6
c
helyébe
4
é
-t írunk, akkor a következőre jutunk:
Ebből viszont az következik, hogy
T
-nek van
6-nál kevesebb éllel határolt országa. Tegyük fel
ugyanis az ellenkezőt! Számozzuk meg az országokat az
1,
2, …,
l
számokkal, és jelöljük
h
i
-vel az
i
-edik országot határoló élek számát! Minthogy
minden él két különböző országnak közös határszakasza,
h
1
+
h
2
+
…
+
h
l
=
2
é
. Feltevésünk szerint minden
i
-re
h
i
≥
6
, tehát a bal oldalt nem növeljük, ha minden
h
i
helyett
6-ot írunk. Ekkor azt kapjuk, hogy
6
l
≤
2
é
. Ez pedig lehetetlen, mert
(
∗
)
szerint
2
é
12-vel kevesebb, mint
6
l
. Tehát
T
tartalmaz
2,
3,
4 vagy
5 éllel határolt országot.
Ha
T
tartalmaz egy kétélű
L
országot, akkor azzal pontosan két másik ország
szomszédos (10/a. ábra). Csatoljuk
L
-et valamelyik szomszédjához, pl.
L
1
-hez (10/b. ábra)!
Így
T
-ből egy szabályos
T
′
térképet állítottunk elő. Elég kimutatni, hogy
T
′
5 színnel jól színezhető, Ebből ugyanis következik,
hogy
T
5 színnel jól színezhető, mert
T
′
színezésekor
L
1
-hez és
L
2
-höz az
5 színből kettőt használunk fel. A többi
3 szín bármelyikével színezhettük az újból
visszaállított
L
országot, és máris jól színeztük
T
-t
5 színnel.
Ha
T
tartalmaz egy háromélű
L
országot, akkor azzal pontosan
3 ország szomszédos. Az előbbi utat követve,
L
visszaállításakor még mindig
2 szín közül választhatunk.
Ha
T
tartalmaz egy négyélű
L
országot, akkor azzal
3 vagy
4 ország lehet szomszédos, amint azt a 11/a. és
11/b. ábra mutatja. Az előbbi utat most is követhetjük, de ahhoz,
hogy
T
′
ismét szabályos legyen, a 11/a. ábra esetén
L
-et nem szabad
L
2
-höz csatolnunk. A visszaállításkor
L
számára még mindig marad
2, ill.
1 szín.
Ha
T
tartalmaz egy ötélű
L
országot, akkor a vele szomszédos országok között
biztosan van kettő, amelyek nem szomszédosak. Mert ha pl.
L
szomszédai
L
1
,
L
2
,
L
3
,
L
4
,
L
5
, és
L
2
szomszédos
L
4
-gyel, akkor a 12. ábrából
látható, hogy
L
3
nem lehet szomszédos sem
L
1
-gyel, sem
L
5
-tel.
T
′
-t most
L
két élének törlésével állítjuk elő:
L
1
és
L
3
felé törlünk egy-egy élt. Ha
T
′
jól színezhető
5 színnel, akkor
T
is, mert
T
′
színezésekor
L
szomszédaihoz mindössze
4 színt használunk fel (
L
1
és
L
3
ugyanazt a színt kapja), és így
L
számára a visszaállításkor marad még egy
szín.
Okoskodásunk szerint elegendő azt bizonyítanunk, hogy a
felsorolt redukciókkal nyert
T
′
jól színezhető
5 színnel. De
T
′
ismét szabályos térkép, tehát érvényes rá a
(
∗
)
összefüggés, amiből viszont következik, hogy
T
′
szintén tartalmaz
2,
3,
4 vagy
5 élű országot. Ennélfogva redukciós eljárásunkat
addig folytathatjuk, amíg csupán
5 ország nem marad. Azt
5 színnel tudjuk jól színezni, és így eljárásunkból
következik, hogy
T
is jól színezhető
5 színnel. Az I. és II. figyelembevételével pedig
azt nyertük, hogy bármilyen normál térkép
5 színnel jól színezhető.