Teorema dei cinque colori

Il teorema dei cinque colori è un risultato della teoria dei grafi, che afferma che, dato un piano suddiviso in regioni connesse (come una mappa politica delle regioni di uno Stato), queste possono essere colorate utilizzando non più di cinque colori, in modo tale che non esistono due regioni adiacenti con lo stesso colore. Analogamente, afferma che ogni grafo planare può essere colorato con cinque colori in modo che due vertici adiacenti siano di colore diverso. È stato dimostrato alla fine dell'Ottocento da Percy John Heawood.

Questo teorema è una conseguenza del più forte teorema dei quattro colori, ma la dimostrazione di quest'ultimo è molto più complessa, ed è stata ottenuta solo nel 1976, da Kenneth Appel e Wolfgang Haken con l'ausilio di un computer.

La dimostrazione di Heawood si basa su una dimostrazione fallace del teorema (allora congettura) dei quattro colori pubblicata nel 1879 da Alfred Kempe; undici anni più tardi, Heawood trovò in essa un errore, ma riuscì a modificarla per dimostrare il teorema dei cinque colori. Essa si basa su un procedimento di riduzione, in cui a partire da una mappa assegnata si diminuisce il numero di regioni presenti senza diminuire il numero di colori necessario per colorarla; al termine del procedimento, si ottiene una nuova mappa di cinque o meno regioni, che può ovviamente essere colorata con cinque colori.

Vi sono sostanzialmente sei processi diversi di riduzione; ad esempio, uno di questi è fondere regioni interamente circondate da un'altra in quest'ultima: se si hanno a disposizione almeno due colori, sarà possibile, una volta colorata la mappa "ridotta", scegliere per la prima regione un colore diverso dalla seconda. Due di questi procedimenti, tuttavia, richiedono di avere a disposizione almeno cinque colori, e quindi non possono essere applicati per dimostrare il teorema dei quattro colori.