Neliväriongelma
Neliväriongelma, nykyisin neliväriteoreema, on verkko- eli graafiteoriaan liittyvä ongelma, jonka mukaan jokainen tasokartta voidaan värittää neljällä eri värillä siten, että millään kahdella vierekkäisellä samanvärisellä alueella ei ole yhteistä rajaa. Ongelman esitti De Morganin oppilas Francis Guthrie vuonna 1852.[1] Raja tarkoittaa rajaviivaa, ei rajapistettä. On melko helposti osoitettavissa, että kartan värittäminen viidellä värillä on mahdollista[2] (Heawoodin lause), mutta neljän värin riittävyys on vaikeammin todistettavissa. Tämän todistivat Kenneth Appel ja Wolfgang Haken vuonna 1976 osoittamalla, että kaikki kartat ovat väritettävissä neljällä värillä jos ja vain jos tietyt 1834 karttaa ovat väritettävissä neljällä värillä. Myöhemmin karttojen lukumäärä pystyttiin pudottamaan 1482:een. Todistus tehtiin tietokoneita apuna käyttäen, mutta kompakti matemaattinen todistus puuttuu edelleen. Neil Robertsonin tutkimusryhmä[3] todisti ongelman uudelleen 1994. Myös Ibrahim Cahit on julkaissut[4] neliväriongelman todistuksen, jossa ei ole mukana tietokonelaskelmia, mutta näitä tuloksia ei ole varmistettu.
