Un gruppo di sei ricercatori ha elaborato una nuova dimostrazione assistita dal computer del teorema dei quattro colori, secondo cui ogni mappa con regioni contigue può essere colorata con quattro colori, in modo che le regioni confinanti siano di colori diversi. La dimostrazione è stata pubblicata online nel marzo 2026 e sarà presentata la prossima settimana alla conferenza annuale Foundations of Computer Science, a New York.
Il lavoro si fonda su un problema che mette alla prova i matematici sin dal XIX secolo. Una prima dimostrazione di Alfred Bray Kempe, annunciata nel 1879, si rivelò lacunosa 11 anni dopo. Il teorema fu infine dimostrato nel 1976 da Kenneth Appel e Wolfgang Haken, che usarono un computer per verificare un vasto insieme di configurazioni di grafi. Una successiva dimostrazione assistita dal computer, pubblicata nel 1997, ridusse il numero di configurazioni da verificare.
Il gruppo più recente comprende i teorici dei grafi Carsten Thomassen, Mikkel Thorup, Ken-ichi Kawarabayashi e Bojan Mohar, insieme ai ricercatori Yuta Inoue e Atsuyuki Miyashita. Il loro approccio individua un insieme di 8.202 configurazioni nei grafi planari e permette di ridurne molte in parallelo. Secondo i ricercatori, ciò rende il processo di colorazione sostanzialmente più efficiente rispetto al metodo precedente, che richiedeva un numero di passaggi con crescita quadratica rispetto al numero di vertici del grafo.
Invece di concentrarsi soltanto sulle aree con gruppi di vertici dotati di pochi collegamenti, il gruppo ha esaminato le parti più piatte di un grafo, in cui i vertici sono collegati secondo disposizioni triangolari. Il lavoro ha inoltre prodotto nuovi strumenti per studiare le proprietà strutturali dei grafi planari, con possibili applicazioni ai problemi di colorazione su altre superfici, tra cui un toro.
La nuova dimostrazione non risolve il desiderio di lunga data di alcuni matematici di disporre di una spiegazione più breve e priva di computer del motivo per cui bastano quattro colori. Thomassen ha detto che vorrebbe vedere una dimostrazione che non faccia affidamento su un computer e che intende continuare a riflettere sulla questione.
Fonti: Smithsonian Magazine.