Contexte : Le Coloriage de Cartes
Le problème du coloriage de cartes consiste à déterminer le nombre minimum de couleurs nécessaires pour colorier n’importe quelle carte géographique de telle sorte que deux régions (pays, départements…) partageant une frontière commune aient des couleurs différentes.
- Ce problème se traduit en théorie des graphes : chaque région est un sommet, et une arête relie deux sommets si les régions correspondantes sont adjacentes. Le problème devient : quel est le nombre chromatique maximal d’un graphe planaire ?
- Le célèbre Théorème des Quatre Couleurs (prouvé en 1976 avec l’aide d’un ordinateur) affirme que quatre couleurs suffisent toujours.
- Le Théorème des Cinq Couleurs est un résultat plus faible mais dont la preuve, beaucoup plus simple, peut être faite à la main. Il a été prouvé par Percy Heawood en 1890.
Théorème des Cinq Couleurs
Toute carte planaire peut être coloriée avec au plus cinq couleurs.
Idée de la Démonstration (par récurrence)
La preuve se fait par récurrence sur le nombre $n$ de régions de la carte.
- Initialisation : Si $n \le 5$, on peut trivialement colorier la carte avec cinq couleurs.
- Hérédité : On suppose que toute carte avec $n$ régions peut être coloriée avec cinq couleurs (hypothèse de récurrence). On considère une carte avec $n+1$ régions.
- Existence d’une petite région : En utilisant la formule d’Euler pour les graphes planaires ($S – A + F = 2$), on peut prouver qu’il existe toujours au moins une région qui a cinq voisins ou moins.
- Suppression de la région : Soit $R$ une telle région. On la « supprime » temporairement et on fusionne ses frontières. On obtient une nouvelle carte avec $n$ régions. Par l’hypothèse de récurrence, cette nouvelle carte peut être coloriée avec cinq couleurs.
-
Réintroduction de la région : On réintroduit la région $R$. Ses voisins sont maintenant coloriés.
- Cas simple : Si les voisins de $R$ (qui sont au plus 5) utilisent moins de cinq couleurs, il reste au moins une couleur disponible pour $R$. Le coloriage est terminé.
- Cas difficile : Le problème se pose si $R$ a exactement 5 voisins, et que ces 5 voisins utilisent les 5 couleurs différentes (disons C1, C2, C3, C4, C5 dans l’ordre horaire).
-
L’argument de la chaîne de Kempe : C’est l’astuce finale. On regarde les voisins de $R$ coloriés en C1 et C3. On considère l’ensemble de toutes les régions de la carte coloriées soit en C1, soit en C3, qui sont connectées au voisin C1. C’est une « chaîne de Kempe ».
- Soit cette chaîne ne contient pas le voisin C3. Dans ce cas, on peut intervertir les couleurs C1 et C3 dans toute cette chaîne. Le voisin C1 de $R$ devient C3. Maintenant, $R$ n’a plus de voisin de couleur C1, qui devient disponible pour colorier $R$.
- Soit cette chaîne contient le voisin C3. Cela signifie qu’il existe un « mur » de régions C1-C3 qui relie les voisins C1 et C3 de $R$. Mais alors, ce mur sépare le voisin C2 du voisin C4. Il est donc impossible de trouver une chaîne de Kempe de couleurs C2-C4 reliant ces deux voisins. On peut donc appliquer l’argument précédent à la paire (C2, C4) pour libérer une couleur.
Importance
- Un pas vers les quatre couleurs : Bien que surpassé par le théorème des quatre couleurs, il a été pendant près d’un siècle le meilleur résultat prouvé rigoureusement à la main.
- Une preuve élégante : Sa démonstration est un classique de la théorie des graphes, illustrant magnifiquement le raisonnement par récurrence et l’argument des chaînes de Kempe.