Théorème des cinq couleurs

Le théorème des cinq couleurs est l'affirmation de la possibilité, à l'aide de cinq couleurs au maximum, de colorier n'importe quelle carte composée de régions connexes, de sorte que toute paire de régions limitrophes apparaisse avec deux couleurs, autrement dit qu'aucune paire ne soit d'une couleur.

Carte où les provinces françaises ont été coloriées en cinq couleurs.

Le théorème des cinq couleurs est un affaiblissement du théorème des quatre couleurs, mais il est beaucoup plus facile à prouver. Sa démonstration utilise les techniques de la tentative de preuve du théorème des quatre couleurs par Alfred Kempe en 1879. Percy John Heawood y a trouvé une erreur 11 ans plus tard et a prouvé le théorème des cinq couleurs en utilisant le travail de Kempe ^[1],[2],[3].

Démonstration

Carte où tous les pays ont cinq voisins, montrant que l'on ne peut utiliser l'existence d'un pays ayant quatre voisins au plus pour prouver le théorème des quatre couleurs. Malgré cela, cette carte est coloriée en quatre couleurs.

Tout d'abord, on associe à la carte un graphe planaire simple ${\displaystyle G}$ en plaçant un sommet dans chaque région, et en reliant deux sommets par une arête si et seulement si les régions correspondantes ont une frontière commune. Le problème se traduit en un problème de coloration de graphe : il faut attribuer une couleur aux sommets du graphe de sorte qu'aucune arête n'ait ses extrémités de la même couleur. ${\displaystyle G}$ étant planaire et simple, c'est-à-dire qu'il peut être plongé dans le plan sans arêtes sécantes et qu'il n'a ni d'arêtes multiples ni boucles, on peut montrer (en utilisant la caractéristique d'Euler du plan) qu'il existe au moins un sommet auquel aboutissent au plus cinq arêtes (i.e. de degré inférieur ou égal à cinq). Remarquons que si on pouvait abaisser le nombre cinq à quatre, on pourrait prouver par cette méthode le théorème des quatre couleurs. Malheureusement il existe des graphes planaires n'ayant pas de sommet de degré inférieur ou égal à quatre, comme par exemple, le graphe icosaédrique qui est 5-régulier (voir un autre exemple ci-contre).

Soit ${\displaystyle v}$ un tel sommet et supprimons ${\displaystyle v}$ de ${\displaystyle G}$ . Le graphe ${\displaystyle G'}$ ainsi obtenu a un sommet de moins que ${\displaystyle G}$, nous pouvons donc supposer par récurrence sur le nombre de sommets que ses sommets peuvent être colorés avec cinq couleurs au maximum.

Si la coloration n'utilise pas les cinq couleurs pour les cinq sommets voisins de ${\displaystyle v}$, on peut colorer ce dernier dans ${\displaystyle G}$ avec une couleur non utilisée par les voisins.

On peut ici inverser les couleurs 1 et 3 dans la composante de Kempe du sommet ${\displaystyle v_{1}}$ sans déroger à la règle des couleurs adjacentes distinctes, et ainsi colorer le sommet ${\displaystyle v}$ avec la couleur 1.

Sinon, on peut supposer que les cinq sommets ${\displaystyle v_{1}}$, ${\displaystyle v_{2}}$, ${\displaystyle v_{3}}$, ${\displaystyle v_{4}}$, ${\displaystyle v_{5}}$ adjacents à ${\displaystyle v}$ dans cet ordre (qui dépend de la façon dont nous écrivons ${\displaystyle G}$) sont colorés avec les couleurs 1, 2, 3, 4, 5 respectivement.

Considérons maintenant le sous-graphe ${\displaystyle G_{1,3}}$ de ${\displaystyle G'}$ composé des sommets colorés uniquement avec les couleurs 1 et 3 et des arêtes qui les relient. Chaque arête relie donc un sommet de couleur 1 à un sommet de couleur 3. Si ${\displaystyle v_{1}}$ et ${\displaystyle v_{3}}$ se situent dans différentes composantes connexes de ${\displaystyle G_{1,3}}$, on peut intervertir les couleurs 1 et 3 dans la composante contenant ${\displaystyle v_{1}}$ (dite composante de Kempe) sans affecter la coloration du reste de ${\displaystyle G'}$. Cela libère la couleur 1 pour ${\displaystyle v}$ et le travail est terminé. Si au contraire ${\displaystyle v_{1}}$ et ${\displaystyle v_{3}}$ se trouvent dans la même composante connexe de ${\displaystyle G_{1,3}}$, nous pouvons trouver un chemin dans ${\displaystyle G_{1,3}}$ les joignant qui se compose uniquement des sommets de couleur 1 et 3.

Passons maintenant au sous-graphe ${\displaystyle G_{2,4}}$ de ${\displaystyle G'}$ composé des sommets colorés uniquement avec les couleurs 2 et 4 et des arêtes qui les relient, et appliquons les mêmes arguments que précédemment. Alors soit on est capable d'inverser la coloration 2-4 sur le sous-graphe de ${\displaystyle G_{2,4}}$ contenant ${\displaystyle v_{2}}$ et peindre ${\displaystyle v}$ avec la couleur 2, soit on peut connecter ${\displaystyle v_{2}}$ et ${\displaystyle v_{4}}$ par un chemin composé uniquement de sommets de couleur 2 et 4. Un tel chemin croiserait le chemin de 1 à 3 couleurs que nous avons construit auparavant depuis ${\displaystyle v_{1}}$ par ${\displaystyle v_{5}}$ étaient en ordre cyclique. Ceci est clairement absurde car cela contredit la planéité du graphe.

Donc ${\displaystyle G}$ peut être coloré en cinq couleurs^[4].

Algorithme de coloration en temps linéaire

En 1996, Robertson, Sanders, Seymour et Thomas ont décrit un algorithme quadratique pour une coloration en quatre couleurs^[5]. Dans ce même article, ils ont décrit brièvement un algorithme pour cinq couleurs en temps linéaire, qui est asymptotiquement optimal.

Liens externes

• Deux (deux ?) minutes pour... le théorème des quatre couleurs.

Références 

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Five color theorem » (voir la liste des auteurs).

1. Jean Lefort, « La catastrophe de Kempe », L'ouvert 50,‎ 1988 (lire en ligne)
2. Georges Gonthier, « Le théorème des quatre couleurs » (consulté le 28 septembre 2021)
3. Jean-Claude Fournier, « Le raisonnement et l'erreur de Kempe », Revue du Palais de la Découverte,‎ janvier 1978, p. 13-18
4. BRICE FEBVRE, REGIS DEMIZIEUX, « Le théorème des cinq couleurs »
5. (en) Robertson, Neil; Sanders, Daniel P.; Seymour, Paul; Thomas, Robin, « Efficiently four-coloring planar graphs" », Proc. 28th ACM Symposium on Theory of Computing (STOC), New York: ACM Press,‎ 1996 (lire en ligne)

• Portail des mathématiques