Théorème des cinq couleurs

Carte où les provinces françaises ont été coloriées en 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.

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 Modèle:,Modèle:,.

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 $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. $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 $v$ un tel sommet et supprimons $v$ de $G$ . Le graphe $G^{\prime }$ ainsi obtenu a un sommet de moins que $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 $v$, on peut colorer ce dernier dans $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 $v_1$ sans déroger à la règle des couleurs adjacentes distinctes, et ainsi colorer le sommet $v$ avec la couleur 1.

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

Considérons maintenant le sous-graphe $G_{1,3}$ de $G^{\prime }$ 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 $v_1$ et $v_3$ se situent dans différentes composantes connexes de $G_{1,3}$, on peut intervertir les couleurs 1 et 3 dans la composante contenant $v_1$ (dite composante de Kempe) sans affecter la coloration du reste de $G^{\prime }$. Cela libère la couleur 1 pour $v$ et le travail est terminé. Si au contraire $v_1$ et $v_3$ se trouvent dans la même composante connexe de $G_{1,3}$, nous pouvons trouver un chemin dans $G_{1,3}$ les joignant qui se compose uniquement des sommets de couleur 1 et 3.

Passons maintenant au sous-graphe $G_{2,4}$ de $G^{\prime }$ 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 $G_{2,4}$ contenant $v_2$ et peindre $v$ avec la couleur 2, soit on peut connecter $v_2$ et $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 $v_1$ par $v_5$ étaient en ordre cyclique. Ceci est clairement absurde car cela contredit la planéité du graphe.

Donc $G$ peut être coloré en cinq couleurs.

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