Lau koloreen teorema

Lau koloreen teorema grafoak koloreztatzeko teorema bat da eta honek ondorengoa dio: eskualde auzokidez osaturiko edozein mapa, oso korapilatsua izanda ere, lau kolorez margo daiteke, aldameneko bi eskualdek beti kolore ezberdinak dituztela.

Lau kolorez margotutako mapa.

Hiru kolorerekin ordea, ezin da edozein mapa margotu[1]. Bost kolorerekin berriz, bai, teorema frogatzeko errazagoa izanik.

Lau koloreen problema lehenengo aldiz Francis Guthriek planteatu zuen 1852. urtean[1]. Planteatu eta mende bat igaro ostean, 1976. urtean, Kenneth Appelek eta Wolfgang Hakenek problema frogatu zuten konputagailu baten laguntzarekin[2].