Théorème des cinq couleurs — Wikipédia

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.

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].

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.

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].

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.

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

• (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).

• Portail des mathématiques