Deux (deux ?) minutes pour le théorème des 4 couleurs

Un théorème qui ne paye pas de mine, mais l'histoire de sa démonstration reste malgré tout assez intéressante : le théorème des couleurs !

Script + commentaires :
Mea culpa par avance pour les couleurs utilisées dans la vidéo. Je reconnais que le vert et le jaune utilisés sont malheureusement un peu trop proche...

    En 1852, Francis Guthrie s’amuse à colorier une carte des cantons d’Angleterre et remarque que 4 couleurs suffisent. En bon mathématicien qu’il est, il se demande si c’est généralisable à n’importe quelle carte. Le problème s’avèrera plus compliqué que prévu, puisque la réponse n’arrivera qu’un siècle plus tard. Ca tombe bien, j’ai 2 minutes pour en parler. Avez-vous reconnu les cartes utilisées dans cette intro ?...

Voici la carte des 12 régions française métropolitaine continentales. Est-il possible de les colorier de façon à ce que deux régions partageant une frontière soient toujours de couleur différente ? Il est évident que oui, il suffit de prendre 12 couleurs différentes, et le tour est joué… Mais peut-on colorier proprement la carte avec seulement 5 couleurs ? 4 couleurs ? 3 couleurs ou 2 couleurs ? Mettez cette vidéo en pause quelques minutes pour y réfléchir, puisque je vais spoiler la réponse tout de suite.

Si vous ne vous y prenez pas n’importe comment, vous pourrez sans difficulté obtenir un coloriage avec 5 couleurs. Si vous y consacrez quelques minutes supplémentaires, un coloriage en 4 couleurs devrait se montrer. Par contre, colorier la carte avec seulement 3 couleurs risque de vous poser quelques problèmes. On sent que ça bloque, sans trop savoir pourquoi. Il est cependant clair qu’une coloration à 2 couleurs est impossible, la Bretagne, la Normandie et les Pays de la Loire sont par exemple clairement de couleur différente.
Sur cette carte de la France, il n’existe aucun groupe de 4 régions qui sont toutes voisines deux à deux, comme on pourrait en trouver sur la carte d’Europe autour du Luxembourg, sur la carte d’Afrique du côté du Malawi ou sur la carte d’Amérique autour du Paraguay. Pour prouver que la carte de France demande au minimum 4 couleurs, il faut donc réfléchir un tout petit peu plus, et observer ce groupe de 6 régions. Si je ne dispose que de 3 couleurs, disons rouge, vert et bleu, je peux colorier l’ïle de France en rouge, les Hauts-de-France en vert et le Grand-Est en bleu. Cela oblige la Bourgogne-Franche-Compté à être verte et le Centre-Val-de-Loire à être bleu. La Normandie est donc bordée par trois régions de couleurs nécessairement différentes, il faut une quatrième couleur.
Bref, 3 couleurs ne suffisent pas pour colorier la carte de France, alors que 4, si. Et c’est justement ça l’objet du théorème des 4 couleurs : 4 couleurs suffisent toujours pour colorier n’importe quelle carte de façon à ce que deux régions adjacentes soient toujours de couleur différente. Il n’existe aucun contre-exemple.

Quand Francis Guthrie observe en 1852 ce phénomène sur sa carte d’Angleterre, il s’empresse d’en parler à son ancien professeur, Auguste de Morgan. Intrigué par le problème mais sans réponse, il en parle à William Hamilton, qui lui répond gentiment qu’il a d’autre projets plus intéressant pour le moment que de colorier des cartes. Malgré tout, De Morgan persiste et parle de ce problème à tout son entourage, dont Arthur Cayley qui écrira le premier article décrivant les difficultés de la question.

Revenons au problème. Les cartes dont on parle sont composées de plusieurs pays ou régions séparés les unes des autres par des frontières. Si des régions se touchent seulement en un point, on ne les considérera pas comme voisines. Ainsi, deux régions opposées par un sommet autour d’un quadripoint peuvent être colorée de la même façon, comme c’est le cas aux Etats-Unis au point frontière entre l’Arizona, le Colorado, le Nouveau-Mexique et l’Utah. On supposera aussi qu’une région n’a pas de frontière avec elle-même, ce qui serait de toute façon complètement absurde. On supposera enfin que les régions que l’on considère sont connexe, c’est à dire, toujours en un seul morceau. Si on commence à autoriser les enclaves et exclaves, on pourra facilement construire des cartes où 8 régions sont toutes adjacentes deux à deux, ce qui fournirait un contre-exemple. Cette hypothèse rend donc ce théorème complètement sans intérêt pour les cartographes, puisque les régions sont rarement d’un seul tenant, ne serait-ce qu’à cause des iles. La Russie, à cause de l’oblast de Kaliningrad non rattachée au reste du pays, fournit un autre exemple de situation problématique.

Bref, le théorème des 4 couleurs énonce que n’importe quelle carte peut être colorée proprement avec seulement 4 couleurs ou, comme le disent les mathématiciens, “4-colorables”. Mais pourquoi est-ce vrai ? N’existe-t-il vraiment aucune carte demandant nécessairement 5 couleurs ? À vrai dire, c’est loin d’être évident. Quand on cherche à la main la carte qui demande au moins 5 couleurs, on passe son temps à presque la trouver, avant de se rendre compte que, non, 4 couleurs suffisent.

Un premier argument simple qui laisse penser qu’un contre-exemple est difficile à trouver, c’est qu’il est absolument impossible de trouver une carte où 5 régions sont toutes voisines deux à deux. On peut prouver ça à l’aide de la formule d’Euler, que l’on avait déjà utilisé pour prouver cette histoire de maisons et d’usines.

Sans rentrer dans les détails non plus, cette même formule d’Euler implique pour toutes les cartes un fait important : il y existe toujours quelque part une région qui possède 5 frontières ou moins. Ce lemme est essentiel pour prouver que toute carte est colorable avec, non pas au plus 4 couleurs, mais au plus 6 couleurs. C’est mieux que rien !

Prenons une carte composée de 7 régions. D’après ce que l’on vient de voir, il y existe au moins une région qui possède moins de 5 frontières. On en choisit une, et on la supprime. Notre carte possède donc maintenant 6 régions, et je peux naturellement la colorier avec 6 couleurs. Replaçons alors la région retirée. Puisque celle-ci n’avait pas plus de 5 frontière, il reste donc au moins une couleur de disponible. Ceci prouve donc que toute carte à 7 régions est 6-coloriable.
L’argument fonctionne aussi pour les cartes à 8 régions. Il y existe un région à 5 frontière que l’on retire. On a alors une carte à 7 régions, que l’on vient de prouver comme étant 6-coloriable. On replace la région retirée, et le tour est joué. De proche en proche, on peut donc prouver qu’une carte à 9 régions, à 10 régions, et, finalement, à n’importe quelle nombre de régions, est 6-coloriable. C’est ce que l’on appelle une démonstration par récurrence. Pour prouver qu’une propriété sur les cartes est vraie, il suffit de prouver dans un premier temps qu’elle est vraie pour les petites cartes puis, dans un deuxième temps, de montrer que si la propriété reste vraie lorsque l’on incrémente le nombre de régions.

Enfin bon. Ce théorème des 6 couleurs, c’est sympa, mais on peut faire mieux. Prouvons que toute carte est 5-coloriable ! Pour cela, il n’y a pas vraiment le choix, il faut à nouveau procéder par récurrence.
Déjà, il est assez clair que toute carte possédant 5 régions ou moins peut être colorée avec 5 couleurs. Ça, c’est la première étape de la récurrence, l’initialisation.
Pour la deuxième étape, on va prouver que, quelque soit l'entier N (aurais-je du rajouter pour être plus rigoureux), si toutes les cartes à N régions sont 5-colorables, alors toutes les cartes à N+1 régions le sont aussi. Ce N pouvant désigner n’importe quel nombre, cette deuxième étape implique que puisque la propriété est vraie au rang N=5, elle l’est aussi au rang N=6, et donc au rang N=7, et ainsi de suite. Bref, allons-y.

Voici une carte possédant N+1 régions. On émet l’hypothèse de récurrence que toute carte à N région est 5-coloriable. Ainsi, si je retire n’importe quelle région de cette carte, il existera un coloration à 5 couleurs. Comme précédemment, on va supprimer temporairement une région possédant 5 frontières, ou moins. Appelons X cette région retirée.  On obtient donc une carte à N région, qui est selon l’hypothèse de récurrence 5-colorable.

Remettons alors la région X retirée. Si celle-ci comptait strictement moins de 5 frontières, on aura aucun mal à lui attribuer une couleur. De même, si parmi les 5 régions frontalières, on retrouve deux fois la même couleur, on peut sans soucis colorier la région.

Il reste alors un cas qui pose problème : comment peut-on s’en sortir si les 5 régions frontalières à X sont toutes de couleur différente ? Eh bien, il va falloir toucher à la coloration du reste de la carte. Disons qu’autour de X se trouvent, dans l’ordre, une région blanche, bleu, jaune, rouge puis verte. On va considérer, en partant de la région voisine verte, l’ensemble des régions de la carte que l’on peut atteindre en ne passant que par les régions vertes et jaune. On appelle cet ensemble une composante de Kempe, du nom de Alfred Kempe qui a pour la première fois démontré le théorème des 4 couleurs. L’intérêt, c’est que dans cette composante verte et jaune de Kempe, il est possible d’inverser les couleurs vertes et jaunes sans que cela ne pose de problèmes.
Deux éventualités alors. Si la région jaune voisine de X ne se trouve pas dans notre composante de Kempe, alors on peut inverser la composante, ce qui libère la couleur verte, et c’est gagné. Dans le cas contraire, c’est qu’il existe un trajet jaune et vert liant les régions voisines jaune et verte. L’existence de ce trajet empêche alors l’existence d’un autre trajet rouge et bleu liant les voisines rouge et bleues de X, puisque deux trajets de couleurs différentes ne peuvent pas se croiser. On peut dont inverser la composante bleue rouge de Kempe partant du voisin bleu de X, ce qui libérera la couleur bleue.
Bref, quitte à modifier la coloration du reste de la carte, il est possible d’attribuer une couleur à cette région supplémentaire X. Ainsi, si toute carte à N région est 5-colorable, alors toute carte à N+1 régions est 5-colorable. On vient donc de démontrer par récurrence que toute carte est 5-colorable !

Mais comment faire mieux ? Comment s’y prendre pour prouver que toute carte peut être coloriée avec 4 couleurs ? On est bien sûr tenté d’utiliser un raisonnement par récurrence similaire à celui de la démonstration du théorème des 5 couleurs. C’est justement ce que Alfred Kempe a tenté de faire en 1879, fournissant la première démonstration du théorème des 4 couleurs. Le succès fut malheureusement de courte durée, puisque 11 ans plus tard, Percy John Heawood débusque une erreur dans la démonstration. Il ne s’arrête pas là, puisqu’il prouve au passage que l’argument principal de Kempe, l’inversion des couleurs au sein d’une même composante, est inutilisable dans certain cas. Il donne même un exemple, qui ressemble à peu près à ceci. Quand on retire la région X, au nord, on peut colorier la carte comme ceci. Cette région nord compte 5 régions voisines, dont deux vertes. Dans ce cas, il sera impossible de libérer l’une des 4 couleurs en procédant simplement à des inversions de couleurs au sein d’une même composante. Vous pouvez par exemple vérifier qu’en transposant les couleurs rouges et jaunes, aucune couleur ne devient disponible. Bref, cette carte détruit complètement le principe de la démonstration de Kempe, retour à la case départ.
Je vous rassure tout de même, cette carte n’est pas un contre-exemple du théorème des 4 couleurs, seulement de la démonstration de Kempe. Un coloriage y est possible, mais il faut faire plus que simplement échanger des couleurs entre plusieurs régions.

Bref : si une carte est coloriable avec 4 couleurs, il n’y a pas d’argument simple qui permet de conclure que l’ajout d’une région la laissera forcément coloriable avec 4 couleurs.

Tout est donc foutu ? Bien sûr que non. Kempe touchait du doigt l’argument qui permettait de conclure, mais n’est pas allé assez loin. En fait, quand on cherche à colorer une carte à partir de la coloration d’une carte plus petite, ce n’est pas toujours une unique région qui faudra retirer, mais plutôt un morceau de la carte, appelée configuration, et qui peut compter plusieurs régions. La démonstration n’en est pas plus simple pour autant.

Plutôt que de chercher à prouver que toutes les cartes peuvent être colorées avec 4 couleurs, on va plutôt chercher à infirmer le contraire : il n’existe aucune carte qui demande au minimum 5 couleurs. Cela revient au même, mais c’est un plus facile à comprendre. Ce que les mathématiciens qui se sont intéressés au problème sont finalement parvenus à prouver non sans difficultés, c’est que si une telle carte contre-exemple existe, alors il en existe toujours une autre strictement plus petite en terme de nombre de régions et de frontières. Comme on ne peut pas diminuer à l’infini la taille d’une carte, un contre-exemple ne peut pas exister. Pour prouver cela, l’idée est donc de chercher à quoi pourrait ressembler la plus petite carte qui demanderait nécessairement strictement plus de 4 couleurs, c’est à dire, chercher un contre-exemple minimal.
Il faut donc passer en revue les propriétés que se doivent de vérifier le plus petit des contre-exemple. Par exemple, on peut dire que dans une telle carte, aucune région ne possède trois frontières ou moins. Sinon, retirer cette région à 3 frontières donne une carte plus petite. Cette nouvelle carte est forcément 4-colorable, sinon, cela contredirait l’hypothèse de minimalité. Cette coloration s’étend doncà la carte initiale, ce qui contredit le fait que c’était un contre exemple. Avec le même genre d’arguments, il est possible de prouver qu’une carte contre-exemple minimale n’a jamais de région comptant exactement 4 frontières.

Ça, c’est ce que les cartes contre-exemples minimales n’ont pas. Mais que peut-on dire qu’elles ont ? Les premiers à s’être penchés sur la question sont Kenneth Appel et Wolfgang Haken, en 1976. Ils sont parvenus à montrer que si une carte est un contre-exemple minimal, alors elle possède forcément l’une des configurations inévitables parmi une liste qu’ils ont mis au point. Le hic, c’est que cette liste compte 1478 configurations, et qu’il faut toutes les analyser une par une.
Prenons par exemple la configuration suivante, appelé losange de Birkhoff. En remplaçant cette configuration par celle-ci, on obtiendra une carte plus petite, donc coloriable avec 4 couleurs. On peut alors montrer, moyennant des échanges de couleurs au sein d’une composante de Kempe que je ne vais pas détailler, que ce coloriage peut toujours s’étendre à la configuration initiale. Bref, cette configuration inévitable qu’est le losange de Birkhoff est ce que l’on appelle “réductible”.
Le travail à faire pour démontrer le théorème des 4 couleurs est donc colossal. Il faut prouver que chacune des 1478 configurations est non seulement inévitable, mais aussi réductible. Faire ce travail à la main est le travail d’une vie, si bien que les deux mathématiciens ont fait un sacrilège aux yeux de la communauté mathématique : ils ont automatisé leur démonstration et laissé leur ordinateur de bureau travailler pour eux la nuit. Après 1200 heures de calcul, l’ordinateur a affiché sa conclusion : toute carte peut être coloriée avec 4 couleurs.  Pour la première fois de l’histoire des mathématiques, l’informatique a donc été indispensable pour mener au bout une démonstration. Il y a alors plusieurs raisons d’être circonspect.
Déjà, il est particulièrement ardu de checker la validité du raisonnement puisqu’elle compte tout de même 600 pages. Une erreur a d’ailleurs été découverte au milieu de la démonstration quelques années plus tard, heureusement sans conséquence. En 1995, une équipe de 4 mathématiciens se replongent dans la démonstration de Appel et Haken, et l’améliorent considérablement, en réduisant à 633 la liste des configurations inévitables. Ils simplifient également la procédure, mais le coeur du raisonnement reste malgré tout confié à l’informatique. Afin de dissiper tous les doutes quant à la validité de cette preuve, George Gonthier la confiera en 2005 au logiciel Coq, un programme qui permet de vérifier mécaniquement qu’une démonstration ne comporte aucune faille de logique. Le mot "mécanique" est utilisé ici de façon abstraite, elle traduit simplement le fait que le programme va analyser la démonstration ligne par ligne et vérifier si chacune d'entre elle est logiquement valable. Dans une démonstration traditionelle de mathématicien, il existe toujours des zones de floue, où des petites parties de la démonstration sont omises (en général, parce qu'elles sont évidentes). Pour vérifier "mécaniquement" une preuve, il faut que la démonstration ne possède aucune de ces zones de floues. Une démonstration vérifiée par ordinateur est donc en fait bien plus fiable qu'une démonstration relue par un mathématicien, mais ne permet pas de comprendre quels argument seraient essentiels au bon fonctionnement d'un théorème. Malgré la relative inaccessibilité de la démonstration, nous sommes aujourd’hui sûr et certain que toute carte peut être coloriée avec 4 couleurs. Le théorème des 4 couleurs est bien un théorème.

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é 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é 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. C’est vraiment trop demander ?

== FAQ ==

Si l'on est motivé, est-ce que cela vaut le coup de faire l'étude des 633 cas de Robertson & co ?
Si ça valait le coup de faire tout le travail à la main, il aurait été fait. Avec la force d'internet aujourd'hui, une démonstration qui demande d'étudier des milliers de cas peut être fait assez rapidement. Seulement, on ne le fait pas simplement parce que la démonstration n'est en elle même pas particulièrement passionnante. Il s'agit juste des mêmes arguments répétés des milliers de fois dans des ordres plus ou moins similaires. Ce qui serait intéressant, ça serait de trouver des manières radicalement différente de procéder !

Peut-on généraliser ce théorème à d'autres surfaces (sphère, tore, etc.) ou à d'autres dimensions ?
Oui, et cela réserve quelques surprises ! Le théorème des couleurs est un théorème du plan, mais il s'étend sans modification à la sphère : toute carte sur une sphère peut être-coloriée avec au plus 4 couleurs. Pour le tore, c'est différent, puisque certaines cartes demandent jusqu'à 7 couleurs (mais jamais plus). Cette propriété a d'ailleurs été démontrée par Heawood bien avant que le théorème des 4 couleurs du plan. De façon plus générale, si une carte est dessiné sur une surface bornée dont la caractéristique d'Euler est χ, alors on peut la colorier en utilisant au plus

couleurs. ⎣x⎦ représente la partie entière de x. La caractéristique d'Euler χ d'une surface étant le nombre que l'on trouve avec la formule S-A+F lorsque l'on y dessine un graphe.

Il n'y a par contre aucune généralisation aux dimensions supérieures. Dès la dimension 3, on peut facilement fabriquer des "cartes 3D" où chaque région touche chacune autre région, et ce avec un nombre de régions arbitrairement grand, à la façon des neurones.

Existe-t-il des cas où 3 couleurs suffisent ?
Evidemment, mais on cherche 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 :
Historique du problème : The four colour theorem, J J O'Connor and E F Robertson
"Contre-exemple" de Gardner : Martin Gardner's April Fool's Map sur mathforum.org
Démonstration de Appel et Haken : Every planar map is four colorable. Part I: Discharging, K. Appel, W. Haken
Démonstration de Robertson & co : A new proof of the four-colour theorem, N. Robertson, D. P. Sanders, P. Seymour, R. Thomas
Résumé de la démo de Robertson & co : The Four Color Theorem, R. Thomas
Résumé de la démo de Robertson & co (en français) : Le théorème des quatre couleurs, Georges Gonthier
A propos de la démonstration de Kempe : How false is Kempe’s proof of the Four Color Theorem? Part II, E. Gethner & cie
Preuve que le graphe de Errara est bien un contre-exemple de la démo de Kempe : Proof that the Errera Graph is a narrow Kempe-Impasse, P. Heining
Preuve formelle de G. Gonthier : Formal proof - the four-color theorem, G. Gonthier
Preuve que le diamant de Birkhoff est réductible : Birkhoff diamond, I. Dupree, E. Zeidan, S. Auciello.
Groupes de 4 régions deux à deux voisines :List of sets of four countries that border one another, Wikipédi

Comments

[eric]

Il y a encore quelqu'un qui lis les commentaire ? J'ai quelque idée a proposé !

[timolea]

Bavo pour cet exposé. Je ne suis pas sûre d'avoir tout compris, mais ça me donne envie de colorier des cartes ou des zentangles. Et je ne prendrais que 4 crayons. C'est bien suffisant ...