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

[D]

L belsejében levő országcsoportokat kössük össze az

[D]

L -et körülvevő határvonalhoz vezető útszakaszokkal (szaggatott vonalak). Ezeket a szakaszokat bővítsük ki egy-egy

[D]

L -ben fekvő országgá (7/b. ábra). Így

[D]

L -ből elemi felület lesz. A felvett új

[D]

L 1 és

[D]

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

[D]

P -ből induló határvonalakat csak egy-egy pontban metszi (8/b. ábra). E kör belsejét csatoljuk az egyik

[D]

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

[D]

L ország a

[D]

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

[D]

T országainak számát

[D]

l -lel, éleinek számát

[D]

é -vel és csúcspontjainak számát

[D]

c -vel!

[D]

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

[D]

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, …,

[D]

l számokkal, és jelöljük

[D]

h i -vel az

[D]

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,

[D]

h 1 + h 2 + … + h l = 2 é . Feltevésünk szerint minden

[D]

i -re

[D]

h i ≥ 6 , tehát a bal oldalt nem növeljük, ha minden

[D]

h i helyett 6-ot írunk. Ekkor azt kapjuk, hogy

[D]

6 l ≤ 2 é . Ez pedig lehetetlen, mert ( ∗ ) szerint

[D]

2 é 12-vel kevesebb, mint

[D]

6 l . Tehát

[D]

T tartalmaz 2, 3, 4 vagy 5 éllel határolt országot.

Ha

T tartalmaz egy kétélű

[D]

L országot, akkor azzal pontosan két másik ország szomszédos (10/a. ábra). Csatoljuk

[D]

L -et valamelyik szomszédjához, pl.

[D]

L 1 -hez (10/b. ábra)!

Így

T -ből egy szabályos

[D]

T ′ térképet állítottunk elő. Elég kimutatni, hogy

[D]

T ′ 5 színnel jól színezhető, Ebből ugyanis következik, hogy

[D]

T 5 színnel jól színezhető, mert

[D]

T ′ színezésekor

[D]

L 1 -hez és

[D]

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

[D]

L országot, és máris jól színeztük

[D]

T -t 5 színnel.

Ha

T tartalmaz egy háromélű

[D]

L országot, akkor azzal pontosan 3 ország szomszédos. Az előbbi utat követve,

[D]

L visszaállításakor még mindig 2 szín közül választhatunk.

Ha

T tartalmaz egy négyélű

[D]

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

[D]

T ′ ismét szabályos legyen, a 11/a. ábra esetén

[D]

L -et nem szabad

[D]

L 2 -höz csatolnunk. A visszaállításkor

[D]

L számára még mindig marad 2, ill. 1 szín.

Ha

T tartalmaz egy ötélű

[D]

L országot, akkor a vele szomszédos országok között biztosan van kettő, amelyek nem szomszédosak. Mert ha pl.

[D]

L szomszédai

[D]

L 1 ,

[D]

L 2 ,

[D]

L 3 ,

[D]

L 4 ,

[D]

L 5 , és

[D]

L 2 szomszédos

[D]

L 4 -gyel, akkor a 12. ábrából

látható, hogy

L 3 nem lehet szomszédos sem

[D]

L 1 -gyel, sem

[D]

L 5 -tel.

[D]

T ′ -t most

[D]

L két élének törlésével állítjuk elő:

[D]

L 1 és

[D]

L 3 felé törlünk egy-egy élt. Ha

[D]

T ′ jól színezhető 5 színnel, akkor

[D]

T is, mert

[D]

T ′ színezésekor

[D]

L szomszédaihoz mindössze 4 színt használunk fel (

[D]

L 1 és

[D]

L 3 ugyanazt a színt kapja), és így

[D]

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

[D]

T ′ ismét szabályos térkép, tehát érvényes rá a ( ∗ ) összefüggés, amiből viszont következik, hogy

[D]

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

[D]

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ő.