QUATRE COULEURS PROBLÈME DES

Résolu en 1976 par Kenneth Appel et Wolfgang Haken de l'université d'Illinois, le problème des quatre couleurs offre une triple particularité : sa popularité, due à la simplicité suggestive de son énoncé ; les nombreux efforts faits pour le résoudre, qui ont fécondé toute la branche de la topologie combinatoire appelée théorie des graphes (cf. théorie des graphes, en particulier le chapitre Coloriage) ; sa solution, enfin, qui n'a pu être obtenue qu'avec l'aide très considérable de l'ordinateur : c'est le premier théorème général établi par cette voie.

Position du problème

On veut colorier une carte géographique tracée sur le plan (ou la sphère) de manière que deux régions voisines soient toujours de couleurs différentes. Précisons que chaque région est connexe (d'un seul tenant) et que deux régions voisines ont au moins une ligne frontière en commun. Dans ces conditions, les cartographes ont constaté que toute carte pouvait être coloriée avec quatre couleurs au plus. C'est cette proposition, appelée conjecture des quatre couleurs, qui a été démontrée par Kenneth Appel et Wolfgang Haken.

Dans les travaux récents, on préfère considérer le graphe dual de la carte, qu'on obtient en choisissant dans chaque région un point intérieur (son chef-lieu) et en reliant par une courbe simple (arête) les chefs-lieux de deux régions voisines. Ce graphe peut être tracé sur le plan sans que deux arêtes se coupent (graphe planaire topologique) ; par nature, il ne comporte pas de boucles. Ce sont les chefs-lieux que l'on colorie. La proposition s'énonce alors :

Les sommets d'un graphe planaire sans boucles peuvent être coloriés avec quatre couleurs de manière que toute arête ait ses extrémités de couleurs différentes.