théorème des quatre couleurs

Prenez une carte et choisissez une couleur pour chaque région. Deux régions qui partagent un morceau de frontière doivent recevoir des couleurs différentes. En revanche, si elles se touchent seulement en un point, elles peuvent garder la même couleur.

Le théorème garantit que quatre couleurs suffisent toujours, quelle que soit la complexité de la carte plane. Il ne dit pas que quatre sont nécessaires pour chaque carte : une carte en damier peut souvent se contenter de deux couleurs.

Le théorème des quatre couleurs est un résultat sur les cartes planes finies et, de façon équivalente, sur les graphes planaires finis. Dans le cadre standard retenu ici, une carte est formée par les régions connexes délimitées par un réseau planaire fini et connexe de frontières, sans croisement hors de leurs extrémités. Deux régions sont dites adjacentes lorsqu'elles partagent un segment de frontière, et non lorsqu'elles ont seulement un point commun. Une coloration correcte attribue une couleur à chaque région sans donner la même couleur à deux régions adjacentes. Le théorème assure l'existence d'une telle coloration avec au plus quatre couleurs.

Pour traduire une telle carte plane finie en graphe, chaque région devient un sommet et chaque frontière commune devient une arête. Le graphe ainsi obtenu est un graphe planaire fini : il peut être tracé dans le plan sans croisement d'arêtes. Colorier la carte revient alors à colorier les sommets du graphe, deux sommets reliés devant avoir des couleurs distinctes.

La borne quatre est universelle et optimale : certaines cartes exigent effectivement quatre couleurs. Pour une carte donnée, le nombre minimal peut toutefois être un, deux, trois ou quatre.

Si une carte plane finie est définie dans le cadre standard et si l'adjacence signifie le partage d'un morceau de frontière, alors ses régions peuvent être coloriées avec au plus quatre couleurs de sorte que deux régions adjacentes aient toujours des couleurs différentes. Sous la forme des graphes : si un graphe fini est planaire, alors ses sommets admettent une coloration correcte utilisant au plus quatre couleurs.

Le résultat s'applique à une carte plane finie du cadre standard : ses régions connexes sont délimitées par un réseau planaire fini et connexe de frontières, sans croisement hors de leurs extrémités. Il faut aussi vérifier que l'adjacence vient d'une frontière commune de longueur non nulle ; le graphe d'adjacence obtenu est alors planaire. La conclusion garantit l'existence d'une coloration en quatre couleurs au plus, mais ne fournit pas nécessairement le nombre minimal pour la carte étudiée.

Si deux régions se rencontrent seulement à un carrefour ponctuel, elles ne sont pas adjacentes au sens du théorème. Si les relations à représenter produisent un graphe non planaire, la garantie de quatre couleurs ne s'applique plus ; il faut alors étudier directement la coloration de ce graphe.

Considérons quatre régions nommées A, B, C et D. Les six voisinages sont A–B, A–C, A–D, B–C, B–D et C–D : chaque région est donc adjacente aux trois autres. Leur graphe d'adjacence est le graphe planaire K₄, représenté par un triangle et un sommet central relié aux trois sommets du triangle.

1. Attribuons le rouge à A.
2. Comme B touche A, attribuons le jaune à B.
3. La région C touche A et B : elle doit recevoir une troisième couleur, ici le noir.
4. La région D touche A, B et C : aucune des trois couleurs déjà utilisées ne convient, donc D reçoit le blanc.
Le résultat utilise quatre couleurs. Le contrôle consiste à parcourir les six arêtes : leurs extrémités ont toujours deux couleurs distinctes. Cet exemple montre que la borne du théorème ne peut pas être abaissée à trois pour toutes les cartes.

Pour colorier une carte, on commence par relever les frontières réellement partagées, puis on construit son graphe d'adjacence. Le théorème garantit qu'une solution avec quatre couleurs au plus existe ; un algorithme de coloration sert ensuite à la trouver.

Dans le modèle idéal d'un réseau cellulaire plan, chaque cellule devient un sommet et chaque paire de cellules voisines une arête. Quatre groupes de fréquences suffisent alors à séparer les cellules adjacentes. Si les interférences portent au-delà des seules voisines, ce graphe doit intégrer ces contraintes supplémentaires et la garantie peut changer.

Lorsque l'objectif est de minimiser le nombre de couleurs sur une carte particulière, le théorème fournit seulement un plafond. Il faut comparer des colorations à une, deux, trois puis quatre couleurs pour déterminer le minimum effectif.

Coloration des régions et coloration des sommets. Sur une carte, les objets colorés sont les régions ; dans le graphe d'adjacence associé, ce sont les sommets. Une frontière commune devient une arête, ce qui rend les deux problèmes équivalents.

Quatre couleurs suffisantes et quatre couleurs nécessaires. Le théorème donne un maximum valable pour toutes les cartes. Une chaîne de régions peut être coloriée avec deux couleurs, tandis que le cas K₄ de l'exemple en exige quatre.

Graphe planaire et dessin sans croisement apparent. Un graphe est planaire s'il possède au moins un tracé sans croisement. Un tracé particulier comportant des croisements ne suffit donc pas à prouver qu'il est non planaire.

Contact en un point. Au sommet où plusieurs régions se rencontrent, deux régions peuvent se toucher sans partager de frontière. Les déclarer adjacentes ajoute une contrainte absente du théorème ; il faut vérifier l'existence d'un segment commun.

Garantie d'existence, pas procédure immédiate. Le théorème affirme qu'une coloration convient, mais cette affirmation ne donne pas à elle seule les couleurs à poser successivement. Une procédure ou un algorithme distinct doit construire la coloration.

Modèle cellulaire idéalisé. La traduction GSM suppose que seules les cellules adjacentes ne peuvent pas partager une bande. Si la portée des interférences crée d'autres voisinages, il faut ajouter les arêtes correspondantes avant de colorier ; le graphe obtenu peut sortir du cadre planaire.

Nombre minimal. Une région isolée demande une couleur ; deux régions adjacentes en demandent deux. Le plafond de quatre ne dispense donc pas d'étudier la carte lorsqu'on cherche l'économie maximale de couleurs.

Le glossaire graphe planaire précise le cadre topologique sur lequel repose le théorème.

La fiche coloration d'un graphe développe le vocabulaire des sommets, des arêtes et du nombre minimal de couleurs.

L'article Colorier les pavés du plan prolonge la question vers d'autres découpages et contraintes de coloration.