Le théorème des quatre couleurs est l'un des résultats mathématiques les plus célèbres.
En 1852, Francis Guthrie* remarque qu'il lui suffit de quatre couleurs pour colorer la carte (pourtant fort complexe) des cantons d'Angleterre, sans donner la même couleur à deux cantons adjacents (ayant une frontière commune). Il écrit donc à son frère Frederick, mathématicien, et lui demande si cette propriété ne serait pas vraie en général pour toute carte plane; celui-ci communique la conjecture au célèbre mathématicien Augustus De Morgan (également son professeur et ayant été celui de Francis) : celui avoue ne pas être capable de répondre à la question. En 1878, le mathématicien Cayley publie (enfin) la question dans un lettre d'une société mathématique fondée par De Morgan.
* F. Guthrie étudia les mathématiques à l'University College de Londres.
Toujours avec les honneurs, il obtient un diplôme d'arts en 1850, puis étudie le droit : il obtient son diplôme en 1852.
Il fut aussi un botaniste amateur très reconnu. Il fut l’initiateur et l'ami du botaniste sud-africain Harry Bolus. Ensemble, ils étudièrent le genre Erica et H. Bolus donna le nom de Guthriae à un genre botanique de la famille des Achariaceae en son honneur. Le nom de Guthrie apparaît dans 14 espèces de plantes.
Le problème s’avèrera plus compliqué que prévu, puisque la réponse n’arrivera qu'en 1976, soit 124 ans après la lettre de Guthrie !
Malgré un énoncé simple, le théorème est resté une conjecture pendant plus d'un siècle, abordée par les plus grands mathématiciens, parfois avec des résultats faux.
Mais ce qui a rendu ce théorème mondialement célèbre, c'est qu'il est le premier (et encore aujourd'hui un des très rares) à avoir été démontré... à l'aide d'un ordinateur !
En effet, en 1976, deux Américains ont réduit (dizaines de milliers de figures à l'appui) le problème à l'étude de 1478 cas critiques (= qui posent problèmes) : ces 1478 configurations ont été étudiées à l'aide de l'ordinateur (plus de 1200 heures de calcul).
Remarque : à ce jour (novembre 2016), aucune preuve qui ne fasse pas appel à l'ordinateur n'a été découverte.
Cela partagea (et partage encore aujourd'hui !) la communauté des mathématiciens, car comment valider une démonstration qui vérifie des milliers de cas par l'utilisation d'un programme informatique ?
Est-ce une vraie démonstration ?
Comment être certain que l'ordinateur n'a pas fait d'erreurs ?
Et un constat pour beaucoup de mathématiciens : faire vérifier des milliers de cas à un ordinateur n'est pas une belle preuve; l'esprit humain doit pouvoir trouver une preuve élégante... Comme le disait le grand mathématicien Henri Poincaré : une théorie est bonne quand elle est belle.
Mais ce n’est pas l’appel à l’informatique qui est le plus décevant dans cette histoire. Quand un problème reste ouvert pendant plus d’un siècle, on s’attend à ce que la démonstration soit mathématiquement passionnante.
Un bon problème de maths, c’est un problème dont la résolution en ouvre des dizaines d’autres.
Quand Andrew Wiles a démontré [en 1994] la conjecture de Fermat ouverte depuis plus de 300 ans, il a surtout fait progresser le programme de Langlands, c’est à dire la compréhension profonde de liens entre arithmétique et géométrie.
Quand Grigori Perelman a démontré [en 2002] la conjecture de Poincaré ouverte depuis presque un siècle, il a développé des outils particulièrement puissants et novateurs en topologie algébrique.
Quand Appel, Haken et leurs successeurs ont démontré le théorème des 4 couleurs, eh bien, il l’ont démontré, et c’est à peu près tout. Les démonstrations sont brutales, et n’apportent pas d’éclairage nouveau à la théorie des graphes.
C’est pour cette raison que les recherches autour de la question sont toujours ouverte. On adorerait débusquer une preuve élégante du théorème des quatre couleurs et qui puisse élargir notre compréhension des mathématiques.[texte tiré de la vidéo de Eljj, voir ci-dessous]
D’autres problèmes plus pratiques peuvent se ramener au problème de la coloration d'une carte, d'un graphe :
- Affecter des fréquences différentes à des cellules voisines dans un réseau de téléphone mobile GSM.
- Organiser un examen suivant les matières que doit passer chaque étudiant. Comment mettre en parallèle plusieurs épreuves sans léser un candidat ?
- Optimiser l'utilisation des machines de travail. Comment mettre en parallèle des fabrications utilisant plusieurs machines ?
- Problème d'incompatibilité. Comment faire cohabiter des personnes ou des animaux en tenant compte de leur incompatibilité ?
- La résolution du Sudoku peut se ramener à un problème de coloration de graphe.
Une vidéo géniale de Eljj pour comprendre les différentes étapes principales de la démonstration de ce célèbre théorème :
Quelques élements historiques intéressants :
- 1852 : Francis Guthrie pose la question du théorème des quatre couleurs.
Via son frère, la question est posé au professeur mathématicien De Morgan, qui s'y intéresse mais refile le bébé au (très célèbre) mathématicien irlandais Sir Rowan Hamilton, qui répond qu'il n'a pas le temps / l'envie (i'm not likely to...) de s'intéresser à ce problème.
De Morgan laissera tout de même un théorème : " il est impossible de disposer cinq régions de telle façon qu'il existe des frontières communes entre tous les couples possibles "; propriété qui laisse penser que quatre couleurs devraient suffire.
- 1879 : Kempe trouve une première ''preuve'' de la conjecture, mais onze ans plus tard Heawood y trouvera une faille majeure malgré les idées intéressantes qui seront à la base de la démonstration finale : il parviendra toutefois à améliorer la démonstration et à en sauver un théorème des cinq couleurs.
Une seconde ''preuve'' par Tait en 1880 sera de même réfutée par Petersen en 1891.
- 1904 : Paul Wernicke, mathématicien allemand, démontre que toute carte doit contenir au moins l'une de ces cinq configurations inévitables :
- 1913 : le père de l'algèbre moderne, Georges Birkhoff, formule la notion de configuration réductible.
- 1922 : Philip Franklin, du M.I.T., développe (sur la base des travaux de Birkhoff) le concept de configurations réductibles et démontre que la conjecture est vraie (quatre couleurs) pour toutes les cartes de moins de 26 couleurs. Cette borne sera améliorée par la suite :
en 1926, Reynolds donne 27;
en 1940, Winn arrive à 35;
en 1970, Ore et Stemple à 39;
en 1976, Mater atteint 95.
Anecdote amusante : Hermann Minkowski (1864-1909) prend ce problème de haut en prétendant que seuls des mathématiciens de troisième catégorie auraient étudié ce problème... ce qui expliquerait qu'il ne soit pas encore résolu. Il entreprend son étude et reconnait quelque temps plus tard :
" J'ai indisposé le ciel par mon arrogance : ma démonstration est, elle aussi, inexacte. "
- 1969 : Heesch trouve des conditions ''presque'' nécessaires et suffisantes pour qu'une configuration soit réductible, et une méthode générale pour trouver un ensemble inévitable de configurations.
- 1976 : Appel et Haken, deux mathématiciens américains, réalisent le programme de Heesch et montrent, dizaines de milliers de figures à l'appui, que toute carte non 4-coloriable doit contenir l'une de 1478 configurations, et, avec 1200 heures de calcul, que chacune de ces configurations sont réductibles.
- 1995 : Robertson, Sanders, Seymour et Thomas mettent à profit la formidable accélération des ordinateurs pour trouver une réalisation nettement plus simple du programme de Heesch, avec seulement 633 configurations; de plus ils automatisent également la preuve d'inévitabilité.
Un théorème de 2016 : Existe-t-il des cas où 3 couleurs suffisent ?
Evidemment, mais on cherche encore aujourd'hui activement une façon de caractériser les cartes qui ne demandent que 3 couleurs.
Il a longtemps été conjecturé (la "conjecture des 3 couleurs de Steinberg") que c'était le cas si la carte ne possède aucun 4-cycle ni 5-cycle (un k-cycle est un chemin passant par k régions et qui revient à son point de départ). Ce n'est que très récemment (en avril 2016, cf ce lien) qu'un contre exemple a été trouvé.
On ne connait donc pas de bon critère permettant de connaitre le nombre minimal de couleurs demandées par une carte.
Sources :
Le site de Gérard Villemin, une mine d'informations (notamment sur l'histoire de ce théorème).
Un extrait (pour la biographie de Guthrie) du livre The Four-Color Theorem: History, Topological Foundations, and Idea of Proof de Rudolf & Gerda Fritsch.
Un article de l'encyclopédie participative Wikipedia.