Parlando di grafi (argomento della puntata in onda il 27 giugno), mi è venuto in mente un problema classico chiamato problema dei quattro colori. Supponete di avere una mappa geopolitica, con delle zone delimitate che rappresentano i vari Stati, e di volerla colorare: ogni area deve essere colorata e l'unico vincolo da rispettare è che non accada mai che due Stati confinanti abbiano lo stesso colore (mentre è perfettamente lecito che Stati diversi abbiano colori uguali, purché non siano confinanti).

Quanti colori servono? Beh, naturalmente se avete abbastanza pastelli diversi riuscite sempre a risolvere il problema: per esempio, se avete a vostra disposizione un colore diverso per ogni Stato il problema è banale. Ma supponete di voler usare il minor numero di colori possibili. La questione fu posta nella seconda metà dell'ottocento e fu per più di un secolo un vero e proprio puzzle per molti matematici. Infatti è facile rendersi conto che ci sono mappe per cui tre colori non sono sufficienti: per esempio, il Belgio confina sia con la Germania che con la Francia, e inoltre la Germania e la Francia sono confinanti fra loro, quindi per colorare Germania, Francia e Belgio servono tre colori diversi. Inoltre, siccome il Lussemburgo confina con tutti e tre gli Stati (Belgio, Germania e Francia), ne consegue che per colorare anche il Lussemburgo servirà per forza un altro colore. Dunque, quattro colori sono necessari. Ma sono sufficienti?

Se provate a mettervi a disegnare mappe "inventate" vi accorgerete presto che è molto difficile creare una mappa in cui servano più di quattro colori. Anzi, a dire la verità è impossibile. Cioè, quattro colori bastano per colorare qualsiasi mappa.

Che c'entra questo con i grafi? Beh, c'entra. Supponete di trasformare ogni nazione in un vertice di un grafo, e di mettere un arco fra due vertici se le due nazioni sono fra loro confinanti. Il problema della colorazione della mappa diventa un problema di colorazione del grafo: dovete colorarne i vertici in modo che vertici adiacenti (cioè, che sono collegati da un arco) non abbiano mai lo stesso colore. Ma di quali grafi stiamo parlando? In effetti, da ogni mappa si può ricavare un grafo, ma qualunque grafo è ricavabile da una mappa?

Ricordatevi che un grafo si disegna mettendo un pallino per ogni vertice, e collegando con un segmento (o con una curva) tutte le coppie di vertici che sono collegati da un arco. Ogni grafo si può quindi disegnare in molti modi diversi, nel senso che la regola appena enunciata non dice dove devono essere piazzati i vertici. Può accadere che disegnando un grafo in un certo modo alcuni archi si intersechino, mentre spostando un po' i vertici si possano evitare questi incroci. Se si riesce a fare questo si dice che il grafo è planare. Un esempio di grafo non planare è il pentacolo (la stella a cinque punte delle BR a cui avete aggiunto un cerchio che unisce ogni punta alle due punte adiacenti): se anche spostate le punte o trasformate i segmenti che le collegano in curve non riuscirete a non farne intersecare almeno due.

E' facile rendersi conto del fatto che i grafi che si ottengono da una mappa sono grafi planari (per dirla in matematichese, sono "tutti e soli" i grafi planari). Quindi il problema delle mappe si può riformulare come segue: qual è il minimo numero di colori necessari a colorare un grafo planare?

Il passaggio da mappe a grafi può sembrare inutile e perfino perverso, ma è vantaggioso nel senso che un grafo non contiene più nessun dettaglio "ininfluente": non ci sono confini, non ci sono astruse linee di demarcazione a zigzag che sono state ottenute seguendo il corso di qualche fiume o in base a un qualche oscuro trattato di pace. Il grafo della mappa contiene solo le informazioni indispensabili per la colorazione.

Già, ma anche come problema di colorazione di grafi la questione è complicata. Il matematico inglese Alfred Kempe, nel 1877, credette di aver trovato una dimostrazione (del fatto che quattro colori sono sufficienti) ma fu sconfessato nel 1890 da Percy Heawood, che trovò un errore nella dimostrazione di Kempe. Heawood riuscì a dimostrare, in compenso, che cinque colori erano sufficienti. Questo, insieme al fatto che tre colori non bastano, lasciava ancora uno spazio scoperto: bastano quattro colori, oppure c'è qualche mappa (pardon: grafo) per cui ne servono cinque?

Si dovette aspettare quasi un secolo per ottenere una soluzione definitiva (?) al problema: dopo una serie infinita di dimostrazioni sbagliate, nel 1976 Kenneth Apple e Wolfgang Hagen dimostrarono che quattro colori sono sufficienti. In realtà, la dimostrazione di Apple e Hagen chiuse la questione dei quattro colori, ma ne aprì un'altra, estremamente spinosa. Infatti, la tecnica usata da Apple e Hagen fu assolutamente insolita per l'epoca: la loro dimostrazione consisteva nel ridurre lo spazio di tutti i grafi planari possibili a un insieme di "controesempi minimali". Se si fosse dimostrato che quattro colori bastavano per colorare tutti questi controesempi, si sarebbe ottenuto come risultato che quattro colori erano sufficienti in generale. I controesempi minimali erano 1936: troppi da esaminare a mano! A quel punto, chiesero aiuto a un computer: i due matematici scrissero un programma che esaminò uno per uno tutti i 1936 esempi minimali e fu in grado di concludere che erano tutti colorabili con quattro colori.

Questo approccio fu oggetto di grandi contestazioni all'epoca: per un matematico, una dimostrazione è un ragionamento che deve convincere della verità di un'asserzione e deve essere esaminabile da parte di un essere umano. Il fatto che un pezzo della dimostrazione di Apple e Hagen fosse stato prodotto da un computer e non potesse essere realisticamente verificato da un singolo essere umano (i 1936 controesempi, una volta disegnati, riempivano ben 400 pagine!) fu considerata (e da molti lo è ancora) un'inaccettabile violazione delle regole implicite nella nozione stessa di dimostrazione.

In realtà, questa obiezione non è del tutto peregrina: se una parte di una dimostrazione è verificata da un programma per computer, occorre dimostrare a parte che il programma usato è corretto. In effetti, il problema di convincere la comunità matematica "ostile" rimane ancora aperto, ed è oggi estremamente attuale (e pertinente per noi): che ruolo può avere un computer nell'assistere il lavoro di un matematico? quanto e in che misura è accettabile che una dimostrazione sia in parte prodotta o verificata solo mediante un programma?