teorema dei quattro colori

Il teorema dei quattro colori

di Pettinato Ginevra

Start

Cosa afferma il teorema?

Il teorema dei quattro colori afferma che data una superficie piana divisa in regioni connesse, come ad esempio una carta geografica politica, sono sufficienti quattro colori per colorare ogni regione facendo in modo che regioni adiacenti non abbiano lo stesso colore.

Storia del teorema

L'ipotesi venne presentata per la prima volta nel 1852, dal matematico Francis Guthrie che, quando era ancora studente, si accorse che per colorare una mappa delle contee britanniche erano sufficienti quattro colori. Negli anni successivi molti matematici tentarono invano di dimostrare il teorema. La dimostrazione del teorema per quattro soli colori è stata fornita nel 1977 da parte di due matematici dell’Università dell’Illinois, grazie all'utilizzo del computer.

Dimostrazione del teorema sulla base della colorazione dei grafi

Utilizzando la teoria dei grafi, si può dire che ogni grafo planare ammette una 4-colorazione. Rappresentiamo ogni stato in una mappa con un punto in corrispondenza della proria capitale e uniamo due punti se e solo se le capitali che essi rappresentano corrispondono a stati adiacenti. In tal modo trasformiamo la carta in un grafo i cui vertici sono le capitali mentre gli spigoli sono i segmenti congiungenti le capitali di stati adiacenti. Si può dimostrare che il grafo che si ottiene in tal modo è sempre planare, cioè si può disegnare in modo che i suoi spigoli si incontrino solo nei vertici.

Quando il teorema non è valido

Il teorema non è valido quando, una regione è formata da più parti con confinanti tra loro. Un esempio del genere è quello degli Stati Uniti d'America. Se prendiamo un mappamondo, si può notare che gli USA sono composti da un blocco centrale di 48 stati, dalle isole Hawaii e da un unico stato isolato non confinante con nessun altro stato confederato: l'Alaska.