Retour à la table des matières

Département de mathématiques de l'Université de La Rochelle

 

Chapitre 4 - Le théorème
des quatre couleurs

 

F - Le principe de la démonstration de Haken et Appel : configurations inévitables et configurations réductibles

Si l'on examine la démonstration du théorème des cinq couleurs, ou la preuve erronée de Kempe, on constate que celles-ci sont constituées de deux étapes bien distinctes :

- dans un premier temps, on montre que le graphe d'incidence doit nécessairement contenir une configuration appartenant à un ensemble assez restreint, formé, ici, de cinq figures : il y a forcément, dans le graphe, un pays possédant 1, 2, 3, 4 ou 5 voisins.

- dans un deuxième temps, on prouve que chacune des configurations de l'ensemble précédent est réductible au sens suivant : on ne peut pas la rencontrer dans un contre-exemple minimal au théorème des cinq couleurs. Prouver la réductibilité d'une configuration consiste donc à montrer que si une carte contient celle-ci et si toute carte plus petite est 5-coloriable, notre carte de départ est elle aussi 5-coloriable. Dans les preuves données plus haut, un tel travail se fait en fusionnant adéquatement certains pays.

Toutes ses remarques restent évidemment valables si l'on tente de prouver le théorème des quatre couleurs, et fournissent une stratégie d'attaque du problème qui est précisément celle adoptée par Kempe.

Un ensemble de configurations suffisamment complet pour que toute carte contienne l'une d'entre elles est appelé ensemble inévitable. L'idée de la preuve de Kempe est donc d'exhiber un ensemble inévitable (les cinq configurations évoquées ci-dessus) formé de configurations toutes réductibles. Si un tel ensemble existe, aucun contre-exemple minimal au théorème des quatre couleurs ne peut exister. La faille dans la preuve de Kempe tient au fait que la réductibilité de la dernière des cinq configurations (un pays entouré par cinq voisins) n'est pas correctement démontrée. C'est néanmoins cette idée qui a guidé Haken et Appel, mais l'ensemble inévitable qu'ils ont dû construire pour prouver finalement le théorème est formé, cette fois, d'un peu moins de 2000 configurations. A ce propos, on peut citer l'estimation donnée au début des années cinquante par l'allemand Heinrich Heesch, qui évaluait à environ 10 000 le nombre d'éléments que devrait nécessairement contenir un ensemble inévitable de configurations réductibles. Au vu de ses estimations, il avait été le premier à estimer que l'utilisation de l'informatique pourrait être d'un grand secours.

Avant de donner un exemple de preuve de réductibilité et d'indiquer le principe guidant la recherche d'un ensemble inévitable, nous avons encore besoin de quelques remarques techniques :

- vu la réductibilité de toute configuration pour laquelle un pays a au plus quatre voisins, on peut se limiter, dans la recherche d'un contre-exemple minimal, aux graphes d'incidence dans lesquels chaque sommet est de degré supérieur ou égal à 5.

- nous avons remarqué que toute configuration dans laquelle quatre pays ou plus ont un point-frontière commun peut être réduite. Il en résulte que, dans un contre-exemple minimal, une telle configuration n'apparaît pas. Cela se traduit, sur le graphe, par le fait que les faces (dans une représentation plane) sont toutes triangulaires, comme l'indique la figure suivante.

 

Les faces sont triangulaires

 

Un graphe d'incidence est dit normal si tous ses sommets sont de degré supérieur ou égal à 5 et si toutes ses faces sont triangulaires. Vu les remarques ci-dessus, tout le travail de recherche d'un ensemble inévitable de configurations réductibles peut se faire en se limitant aux graphes normaux.