A matematikában a négyszín-tétel azt állítja, hogy egy tetszőleges régiókra osztott síkot, akár egy politikai térképet egy ország megyéiről, ki lehet úgy színezni legfeljebb négy szín felhasználásával, hogy ne legyen két azonos színű szomszédos régió. Két régiót akkor nevezünk szomszédosnak, ha nem csak izolált pontokban, hanem egy görbe mentén érintkeznek. A régióknak összefüggőeknek kell lenniük: tehát nem állhatnak különálló részekből, mint nem kevés ország, például Angola, Azerbajdzsán vagy az Amerikai Egyesült Államok.
Az egészen nyilvánvaló, hogy három szín kevésnek bizonyulhat. Ez már egy olyan térképnél is megmutatkozik, ahol egy régiót három másik régió vesz körül (ámbár ha páros számú régió veszi körül, három szín is elég). Nem túl nehéz megmutatni, hogy öt szín elégséges egy térkép kiszínezéséhez.
A négyszín-sejtés volt az első nevezetes matematikai sejtés, amit számítógép használatával sikerült bebizonyítani.
A sejtést először 1852-ben fogalmazta meg Francis Guthrie, amikor megfigyelte, hogy Anglia megyéinek színezéséhez négy színnél nem volt többre szüksége. Sejtését elmondta öccsének, Frederick Guthrie-nek, aki akkor a londoni University College-ben tanult matematikát. 1852. október 23-án az ifjabb Guthrie elmondta a sejtést tanárának, Augustus De Morgannak. (Francis Guthrie később matematikaprofesszor lett Dél-Afrikában.)
De Morgan azonnal fellelkesedett a kérdéstől és még aznap levelet írt Sir William Rowan Hamiltonnak:
"Egy tanítványom megkért, hogy indokoljak meg neki egy tényt, amiről addig nem tudtam, hogy tény – és nem tudom még most sem. Azt állítja, hogy akárhogyan is osztunk fel egy alakzatot, és a részeket különböző színekkel színezzük, úgy, hogy a közös határvonallal rendelkező részek színe különbözik – négy színre szükség lehet, de többre nem – a következő ő példája, arra az esetre, amikor négy színre van szükség. Nem sikerült olyan esetet találni, amikor öt vagy több szín kellene…"
Hamilton is gyorsan reagált: négy nappal később közölte, hogy őt viszont a legkevésbé sem érdekli a kérdés…
Az első publikált hivatkozást Arthur Cayley On the colourings of maps. c. művében találjuk. (Proc. Royal Geography Society 1, 259-261, 1879.)
Számos korai sikertelen próbálkozás volt a sejtés bizonyítására. Alfred Kempe 1879-ben közzétett egy bizonyítást, amit széles körben elfogadtak; egy másik bizonyítás Peter Guthrie Taité volt 1880-ból. Csak 1890-ben mutatta meg Percy Heawood, hogy Kempe bizonyítása hibás volt, majd 1891-ben Julius Peterson talált hibát Tait levezetésében.
1890-ben Kempe hibás bizonyításának felhasználásával Heawood megmutatta, hogy minden síkba rajzolható gráf kiszínezhető öt színnel; lásd ötszín-tétel.
Az 1940-es években jelentős eredményeket ért el Danilo Blanuša horvát matematikus két új snark megtalálásával.
Az 1960-as és 1970-es években Heinrich Heesch német matematikus módszereket dolgozott ki arra, hogy lehetne a számítógépet tételbizonyítás során felhasználni.
|
