A térképeken színezéssel szokás áttekinthetővé tenni az országok rendszerét, mégpedig úgy, hogy egy ország minden részét ugyanolyan színűre, a különböző országokat pedig különböző színűre festik be. Az áttekintést nem zavarja, ha nem szomszédos országok ugyanazt a színt kapják. A színezésnél akkor kell két országot szomszédosnak tekintenünk, ha határvonaluknak van közös szakasza; tehát az 1. ábrán látható

L 1 és

[D]

L 2 nem szomszédos országok.

Egy térképet

p színnel jól színezhetőnek mondunk, ha

[D]

p színnel úgy színezhetők az országai, hogy egy ország színezéséhez a

[D]

p szín közül csak egyet használunk, és a szomszédos országok különböző színt kapnak. A térképek elkészítéséhez célszerű minél kevesebb színt használni. Ha egy térképen pl. 100 ország van, akkor 100 színnel biztosan jól színezhető. De szükséges-e ilyen sok szín? Ha az országaink olyanok, hogy mindegyiknek van egy-egy része mindegyikben, akkor igen, hiszen valamennyi lehet valahol szomszédos. Talán az országok feldaraboltsága miatt van szükségünk ilyen sok színre? Zárjuk most ki ezt a lehetőséget! Nevezzünk egy térképet normál térképnek, ami azt jelenti, hogy bármely országának két tetszőleges pontja összeköthető az országon belül haladó útvonallal. Ilyen országokat összefüggőknek mondunk. Több mint 100 éve Cayley vetette fel a problémát: vajon hány szín elegendő bármilyen normál térkép jó színezéséhez? A 2. ábrán látható

normál térkép négy országának jó színezéséhez 4 szín szükséges, hiszen a négy ország közül bármely kettőnek van közös határa, azaz a négy ország páronként szomszédos. A kérdéses minimális színszám tehát legalább 4. Az eddig felrajzolt normál térképek mindegyikét sikerült 4 színnel jól színezni, de a mai napig senki sem tudta bizonyítani, hogy 4 szín minden normál térkép jó színezéséhez elegendő. Ez a híres négyszín probléma.^[14]

A probléma gyakorlatilag nem túl érdekes, hiszen egyrészt a valóságban nem csupán normál térképek fordulnak elő, másrészt az bebizonyított tény, hogy 5 színnel már bármilyen normál térkép jól színezhető. (Ez az ún. ötszín probléma. Megoldásával a későbbiekben foglalkozunk.) Ennek ellenére a probléma mélyen behatolt a matematika területére, és sokan megkísérelték, hogy a benne rejlő bizonytalanságot feloldják. Az ilyen kísérletek hasznossá válhatnak, mert általuk olyan módszerek birtokába juthatunk, amelyek más, gyakorlatilag is fontos problémák megoldásaihoz vezetnek.

A kutatások eddigi eredményeinek részletes áttekintése messzire vezetne. Itt főleg e tárgykör érdekességeire szeretnénk a figyelmet irányítani.