Il teorema dei quattro colori afferma che qualsiasi mappa disegnata su un piano può essere colorata usando al massimo quattro colori, in modo che nessuna coppia di regioni che condividono un confine abbia lo stesso colore. Due regioni che si toccano solo in un singolo punto possono condividere un colore. Il teorema si applica a qualsiasi mappa, per quanto complessa.
Regions 1, 2, 3, 4 each border multiple others. The left (4) and right (4) regions share no border, so they can share a colour. Exactly 4 colours needed here.
Francis Guthrie congetturò il teorema nel 1852 mentre colorava una mappa delle contee inglesi. Notò che quattro colori sembravano sempre sufficienti, ma non riuscì a dimostrarlo. Il problema mise in difficoltà i matematici per 124 anni. Furono pubblicate e confutate molte false dimostrazioni. Cinque colori bastano sempre e possono essere dimostrati a mano usando la formula di Eulero per i grafi planari.
The four colour theorem took 124 years from conjecture to proof. The 1976 proof was the first major theorem verified by computer.
La dimostrazione del 1976 di Kenneth Appel e Wolfgang Haken fu il primo grande teorema dimostrato con il computer. Ridusse tutte le mappe possibili a 1.936 configurazioni e fece verificare ciascuna da un computer per oltre 1.200 ore di CPU. Molti matematici erano a disagio con una dimostrazione che non poteva essere controllata a mano. Una dimostrazione leggibile dall'uomo, ammesso che esista, resta ancora sconosciuta.
Five outer regions (an odd number) force the ring to use 3 colours: no 2-colouring of a 5-cycle exists. The centre region is adjacent to all five, touching all three ring colours, so it must be a fourth colour. This shows four is genuinely sometimes necessary.
Ogni mappa disegnata su un piano può essere colorata usando al massimo quattro colori, in modo che nessuna coppia di regioni che condividono un confine abbia lo stesso colore. Congetturato da Francis Guthrie nel 1852. Dimostrato da Appel e Haken nel 1976 usando un computer per verificare 1.936 configurazioni, diventando così il primo grande teorema dimostrato con l'assistenza del computer. Una verifica più breve di Robertson, Sanders, Seymour e Thomas nel 1997 ridusse questo numero a 633 configurazioni. Il teorema non vale sul toro, dove possono servire sette colori.