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

 

G - Recherche de configurations réductibles

Les méthodes de démonstration de la réductibilité d'une configuration reposent en général sur l'idée déjà rencontrée de fusion de deux - ou plusieurs - régions. Cette idée, claire en termes de cartes de géographie, se traduit de la manière suivante sur le graphe d'incidence : fusionner deux pays, c'est identifier les deux sommets correspondants, supprimer la frontière qui les séparait et transformer toute frontière extérieure avec l'un ou l'autre en frontière avec le nouveau. Il s'agit donc de supprimer l'arête (ab), d'identifier les sommets a et b en un nouveau sommet a' et de transformer toute arête (ca) ou (cb) en arête (ca'). Une telle opération s'appelle une contraction. Lorsque, par exemple, nous avons fusionné dans la preuve du théorème des cinq couleurs les trois régions O, A et C en une unique région O', la contraction correspondante sur les graphes était la suivante :

 

Un exemple de contraction

 

Nous donnons maintenant un exemple de démonstration de réductibilité, dû à Birkhoff.

Théorème - Soit G un graphe normal. On suppose que G contient un sommet de degré 5 possédant trois voisins consécutifs de degré 5 aussi. Alors G est réductible.

Remarque -  Le mot ''consécutifs'' doit être compris dans son sens le plus intuitif (en tournant dans le sens des aiguilles d'une montre - ou dans l'autre - on rencontre successivement les trois arêtes conduisant à ces sommets de degré 5).

Démonstration - Appelons v0 ce sommet, v1, v2 et v3 ses trois voisins consécutifs de degré 5. On a donc la figure suivante :

 

Le voisinage de v0

 

Du fait de la normalité, la face triangulaire bordée par (v0t6) et (v0v3) est (v3t6). En répétant ce raisonnement, la figure devient

 

Les faces sont des triangles

 

On voit ainsi apparaître un ''cycle séparateur'' (t1, t2, t3, t4, t5, t6). Dans le cas général, c'est l'étude d'une contraction adéquate à l'intérieur de ce cycle qui permet de prouver la réductibilité, c'est-à-dire la possibilité de prolonger un coloriage de ''l'extérieur'' du cycle à l'intérieur de celui-ci. Dans le cas présent, on contracte les six sommets t4, t6, v0, v1, v2 et v3. On obtient la nouvelle configuration

 

Contraction et coloriage

 

Supposons coloré le graphe réduit avec seulement quatre couleurs a, b, g et d. En redéployant la partie contractée de la figure, on en déduit, sans essayer de colorier les vi, un coloriage de la figure tel que les couleurs de (t1, t2, t3, t4, t5, t6) soient

avec x = b ou g, y a (les sommets t4 et t6 sont de la même couleur a car avant le redéploiement ils étaient confondus). On obtient donc six possibilités de coloriage pour ce cycle :

(1) (b, g, b, a, b, a)

(2) (b, g, b, a, g, a)

(3) (b, g, b, a, d, a)

(4) (b, g, d, a, b, a)

(5) (b, g, d, a, g, a)

(6) (b, g, d, a, d, a)

Dans les cas (2) à (6), on vérifie que l'on peut colorier les vi sans nouvelle couleur et sans changement des ti. Par exemple, dans le cas (2) on obtient :

 

Un prolongement simple

 

Dans le cas (1), on constate facilement qu'aucun coloriage des vi ne convient. Comme dans la ''preuve'' de Kempe, on va donc modifier la couleur de certains sommets (mais cette fois avec plus de précautions). Partons du b qui colore t3 et essayons de la transformer en d. Si la chaîne de modifications qui en résulte n'atteint pas t1 et si elle atteint t5, on obtient la nouvelle coloration

qui est le cas (6) et qu'on peut donc prolonger. Si elle n'atteint ni t1 ni t5, la chaîne devient

qui est le cas (4) et là encore on peut prolonger. Sinon, elle atteint (t1). Pour les mêmes raisons, il existe une chaîne de sommets colorés en b ou d qui relie t5 à t1. Il en résulte que la couleur a en t4 peut être permutée avec g sans que cela n'entraîne de conséquence sur la couleur a en t6 ni g en t2 (tous deux sont ''protégés'' par les deux chaînes exhibées au dessus). Finalement, on obtient le coloriage

 

Prolongement utilisant une chaîne de Kempe

 

ce qui achève la preuve de la réductibilité.

Les résultats analogues à celui de Birkhoff sont nombreux, et leur preuve s'appuie sur la considération du ''cycle séparateur'' d'une configuration donnée et le prolongement du coloriage de la figure contractée à un coloriage de la figure déployée, moyennant une éventuelle modification, analogue à celle effectuée ci-dessus. C'est cette partie du travail qui, dans la démonstration sur ordinateur, nécessite les temps de calcul les plus longs. Par exemple, la preuve de la réductibilité de la configuration ci-dessous, dont le cycle séparateur contient 14 sommets, nécessite l'examen de près de 199 291 coloriages.

 

Une des 1482 configurations...