Il teorema dei quattro cinque colori — grafi planari

Il teorema dei quattro colori è famoso, facile da enunciare, difficilissimo da dimostrare (tant'è che qualcuno ancora discute sulla validità della sua dimostrazione). Dice che sono sufficienti quattro colori per colorare una qualsiasi carta geografica in modo tale che due territori confinanti non siano colorati con lo stesso colore.

Naturalmente i Veri Matematici non dicono così: non parlano di carte geografiche (per le quali sicuramente si riuscirebbe a trovare qualche strana configurazione che nemmeno i cartografi più assatanati avrebbero mai immaginato di vedere), ma parlano di grafi planari.

I grafi planari sono molto semplici da descrivere: sono costituiti da un po' di oggetti (vertici) collegati da un po' di segmenti, anche curvilinei (detti spigoli, o archi). Cose così, insomma:

Alcuni grafi possono essere rappresentati senza intersezioni tra gli spigoli, altri no. Per esempio il grafo completo (cioè con tutti i possibili collegamenti) con 4 elementi è fatto così:

e basta poco per capire che si può evitare l'intersezione tra i due spigoli interni riarrangiando un pochino il disegno:

(si può fare anche lasciando la configurazione dei vertici un pochino più simmetrica, ma il programma che sto usando non lo fa in automatico e non so come fare per fargli fare quello che voglio io, quindi pazienza)

Esistono grafi non planari, cioè che non possono in nessun modo essere rappresentati sul piano senza intersezioni tra gli spigoli. Un teorema importante di teoria dei grafi (teorema di Kuratowski) afferma che se un grafo contiene almeno un sottografo omeomorfo (cioè avente la stessa forma) a uno dei due disegnati qua sotto, allora non è planare.

Questo qui sopra è il grafo completo con 5 vertici (per gli amici, K₅).

E quest'altro è il famoso grafo relativo al giochino delle tre case che devono essere raggiunte dai tre fornitori di servizi (acqua, luce e gas, per esempio). Sono entrambi non planari, naturalmente.

Quindi, riassumendo, le carte geografiche di cui si occupa il teorema dei quattro colori sono grafi

• planari, 
• connessi (una carta geografica potrebbe avere due continenti disconnessi, separati da un oceano, ma questo non ci dà fastidio: il nostro problema è colorare un continente alla volta), 
• semplici, cioè tali che due vertici sono connessi da al massimo un solo spigolo (non ha senso dire che i due stati A e B confinano due o più volte, insomma).

E per questo tipo di grafi è valida la seconda più bella formula della matematica, ovvero Facce più Vertici = Spigoli più 2. Dove con facce intendiamo le regioni delimitate dai bordi, compresa quella esterna che ha estensione infinita.

Dopo tutte queste belle definizioni, e grazie anche a Eulero, dimostrare il teorema dei quattro colori dovrebbe essere molto facile.