Il teorema dei quattro cinque colori — la dimostrazione

Dimostriamo il teorema dei cinque colori per induzione. Ovvero: supponiamo che sia possibile colorare come si deve un grafo avente un certo numero di vertici, e facciamo vedere che è possibile colorare anche un grafo avente un vertice in più. Da qui, come in una catena di domino in cui ogni tessera che cade mette in moto una nuova tessera, si deduce che il teorema è vero per ogni grafo.

Quindi: sappiamo che in un qualunque grafo ci deve essere un vertice avente al massimo cinque spigoli che escono da esso. Troviamolo.

Ok, concentriamoci sul vertice blu, immaginiamo che il grafo possa proseguire a partire dai vertici rossi come vuole. Anche se i vertici rossi in questo disegno sono tutti connessi con meno di cinque spigoli, in realtà potrebbero averne molti di più.

Il vertice blu è collegato a meno di cinque vertici, in questo caso quattro.

Bene, se noi rimuoviamo dal grafo il vertice blu, otteniamo un grafo che ha un vertice in meno e, quindi, per ipotesi induttiva, è colorabile con cinque colori. Se aggiungiamo il vertice blu, non ci sono problemi a colorare il tutto: dato che è connesso con solo quattro altri vertici, non sono certamente stati usati tutti i cinque colori. Quindi prendiamo un colore che non abbiamo usato e siamo a posto.

Passiamo al caso difficile: il vertice sul quale abbiamo posto l'attenzione è effettivamente collegato con cinque altri vertici, e abbiamo già usato tutti i cinque colori disponibili.

Scegliamo due colori, per esempio il giallo e il viola, e consideriamo solo i nodi colorati con quei colori, e solo gli spigoli che connettono quei nodi. Può succedere, come in questa figura, che il sottografo contenente solo i due colori sia formato da due o più componenti connesse, separate tra di loro. Ecco qua:

Se le cose stanno così, è facile colorare il grafo con cinque colori: basta invertire i colori di una delle due componenti connesse, e si riesce a liberare un colore da assegnare al vertice nero. Per esempio, se invertiamo i colori della componente in alto, otteniamo questa figura:

Abbiamo liberato il colore viola, che possiamo assegnare al vertice nero, ed ecco fatto.

E se il sottografo che contiene i due colori che abbiamo scelto fosse composto da un'unica componente connessa? Come potremmo fare in questo caso? Vediamo un disegnino:

Se le cose fossero così, dovremmo scegliere altri due colori e ripetere il ragionamento fatto sopra. Domanda: siamo sicuri di trovare una coppia di colori che forma almeno due sottografi sconnessi, come prima? Potrebbe verificarsi il caso in cui ogni coppia di colori che noi scegliamo genera un sottografo avente un'unica componente connessa?

La risposta è no, ma se cercate su internet trovate delle spiegazioni poco convincenti e troppo sbrigative. Dice per esempio wikipedia che se scegliamo altri due colori, per esempio il verde e il blu, allora il sottografo formato solo dai nodi avente quei colori e dagli spigoli che li collegano non può essere composto da un'unica componente connessa, perché si intreccerebbe con il sottografo giallo-viola. Ma non è mica vero, non è difficile immaginare un percorso verde-blu non intrecciato col giallo-viola.

Il fatto è che non è possibile che, comunque noi scegliamo due colori, il sottografo che li contiene sia composto da un'unica componente connessa.

Per dire, se aggiungo un po' di collegamenti posso arrivare a una figura del genere, dove ancora le componenti bicolorate sono tutte connesse:

Posso andare avanti ancora? Posso immaginare che blu e rosso siano collegati tra loro da un'unico cammino bicolorato? Sì, è possibile, ma questo cammino dovrà contenere il nodo verde, oppure tutti gli altri. Se contiene il verde, per esempio, può succedere una cosa del genere:

A questo punto un cammino verde-giallo non potrebbe più essere connesso, perché il verde è all'interno del circuito rosso-blu, mentre il giallo è all'esterno (e questo, attenzione, è il risultato di uno di quei teoremi aventi il rapporto chiarezza enunciato/facilità di dimostrazione elevatissimo: si tratta del teorema della curva di Jordan, che dice che ogni curva chiusa del piano non intrecciata divide il piano stesso in due regioni, una interna e una esterna. Sembra una scemata, ma non è banale per niente).

Quindi, anche in questo caso si riesce a colorare il vertice nero con uno dei cinque colori.

Conclusione: l'induzione funziona, le carte geografiche si possono colorare tutte utilizzando cinque colori al massimo.

Per dimostrare che di colori ne servono quattro servono un computer, tanto tempo a disposizione, e una predisposizione filosofica a fidarsi dell'operato di un programma.