Il celebre problema dei quattro colori nasce storicamente (Francis e Frederick Guthrie, 1852; A. Cayley, 1878) come problema di colorazione di carte geografiche: si vuole che due stati confinanti non abbiano lo stesso colore e ci si domanda se quattro colori siano comunque sufficienti per colorare gli stati di una qualunque possibile carta geografica. Da un punto di vista matematico conviene anzitutto precisare il concetto di carta geografica: gli stati sono regioni del piano connesse (cioè non formate da due o più parti), e due stati si dicono confinanti se hanno una linea di confine in comune (non soltanto un numero finito di punti). Il problema rimane sostanzialmente inalterato se le regioni si trovano, anziché su di un piano, sulla superficie di una sfera (la Terra): in quest’ultimo caso, basta scegliere un punto P interno ad una regione e proiettare la superficie sul piano tangente nel punto diametralmente opposto a P; ci si riporta così al caso di regioni piane. La risposta affermativa al problema , congetturata da P. J. Heawood (1861-1955), che aveva dimostrato che cinque colori sono comunque sufficienti, è stata data soltanto nel 1976 da K. Appel e W. Haken, e costituisce il teorema dei quattro colori. A questa dimostrazione, molto complicata e che per di più fa un uso massiccio del calcolatore, si è giunti attraverso una serie di precedenti "dimostrazioni" presunte; mi limito a citare quelle di B. Kempe del 1879 e di G. Tait del 1880, rispettivamente confutate da Heawood nel 1890 e da Petersen nel 1891. Gli sforzi tesi alla risoluzione del problema hanno dato comunque un importante contributo allo sviluppo della teoria dei grafi ed allo studio della topologia.