Ce problème est connu sous le nom du théorème des quatre couleurs. Il resta un problème non résolu pendant plus d'un siècle. En 1852, Francis Guthrie, mathématicien sud-africain essayait de colorier les cartes des cantons d’Angleterre de telle sorte que deux cantons voisins soient de couleurs différentes et remarqua que seulement 4 couleurs étaient suffisantes.
En bon mathématicien, se pose alors la question de la démonstration et de la généralisation du problème.
Prenez une carte de France par exemple et vous pourrez sans problème colorier les régions avec 10 couleurs, puis 8, puis 6. Avec 5 puis 4 couleurs, il faut commencer à réfléchir à l’organisation des couleurs entre elles
Mais à 3 cela coince souvent. Très rapidement on comprend qu’il faut intégrer une 4e couleur pour éviter que 2 couleurs ne se touchent.
Francis Guthrie expose le problème à son ancien professeur, Auguste De Morgan qui le soumet à Arthur Cayley qui rédigera le premier article décrivant les difficultés du problème. Deux premières démonstrations furent publiées, respectivement par Alfred Kempe en 1879 et Peter Guthrie Tait en 1880. Mais elles se révélèrent erronées.
En 1976, les Américains, Kenneth Appel et Wolfgang Haken, affirment avoir démontré le théorème. La démonstration rend perplexe les mathématiciens car pour la première fois une démonstration mathématique utilise un ordinateur. Le problème de la démonstration du théorème se trouve alors déplacé vers le problème de la validation.
En 2005, le logiciel Coq développé par l’Inria a permis à un ordinateur de complètement vérifier le théorème des quatre couleurs : il faut au MAXIMUM quatre couleurs pour colorier une "bonne" carte. Par exemple, 4 pour un tétraèdre mais 3 pour un cube... Cherchez d’autres exemples où 3 couleurs suffisent.
Texte avec la collaboration de Philippe Grillot et Stéphane Cordier, Institut Denis Poisson.
En complément, voir également les vidéos :
Illustration de Vincent Burille (Zinzo)
Centre-Sciences
Gratuit