Štamparima je poznato da se svaka geografska karta može odštamapati sa četiri boje tako da se dvije zemlje sa zajedničkom granicom oboje različitim bojama.

Matematičari de Morgan i Keli postavili su 1850. godine zanimljiv problem:

Može li se svaka geografska karta u ravni

ili na sferi obojiti s najviše četiri boje

tako da zemlje sa zajendničkom granicom

ne budu obojene istom bojom.

Ovaj problem je imao veliki značaj na dalji razvoj teorije grafova. Iako jednostavno forumulisan, on je veoma težak.

Bilo je bezbroj pokušaja da se riješi. 1890g. Hivud je dokazao da je uvijek dovoljno pet boja da bi se bilo koja politička karta država obojila tako da države sa zajendničkom granicom ne budu obojene istom bojom. Tek 1976g. Apel i Haken su dokazali da je, uz zadane uslove, za bojenje svake geografske karte u ravni ili na sferi potrebno najmanje četiri boje.

Za dokaz im je bilo potrebno oko 1200 časova rada kompjutera.