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

 

D - La démonstration erronée de Kempe. Le théorème des six couleurs. Le théorème des cinq couleurs

Avant de donner la démonstration erronée de Kempe, nous prouvons ici le théorème des 6 couleurs et celui des 5 couleurs.

Théorème - Tout graphe planaire est 6-coloriable.

Démonstration - On raisonne par récurrence sur le nombre n de sommets. Le résultat est évident si n 6. Supposons le vrai pour n et soit G un graphe planaire à n+1 sommets. Le degré de l'un d'eux n'excède pas 5. Colorions avec au plus six couleurs le graphe obtenu en supprimant ce sommet. Il suffit de voir que l'on peut maintenant le colorier aussi. Or, les sommets avoisinants utilisant au maximum cinq teintes, il est possible de colorier le dernier sommet en utilisant la sixième.

Après ce résultat d'une grande simplicité, nous donnons maintenant la preuve du théorème des cinq couleurs. Il s'agit encore d'une démonstration par récurrence, mais au cours de laquelle nous privilégierons l'aspect ``carte''. Par ailleurs, nous donnerons, lorsque c'est possible, des arguments permettant de prouver la possibilité de colorier avec quatre couleurs.

Théorème - Tout graphe planaire est 5-coloriable.

Démonstration - Nous avons vu que notre graphe contient un point dont le degré est inférieur ou égal à 5. En termes de cartes, cela revient à affirmer l'existence d'un pays dont le nombre de pays frontaliers est 1, 2, 3, 4 ou 5. Supposons, toujours par récurrence, l'existence d'un coloriage établie pour toute carte contenant un pays de moins.

Si la carte contient un point où se rencontrent quatre pays ou plus, on vérifie facilement que ces quatre pays ne peuvent tous être frontaliers. Fusionnons d'eux d'entre eux non frontaliers et créons un petit isthme pour rendre ce nouveau pays connexe. La carte qui en résulte est coloriable et après séparation de nos deux pays et écrasement de l'isthme la carte de départ est coloriée avec le même nombre de couleurs (quatre ou cinq suivant le théorème que l'on est en train de démontrer).

 

Réduction par création d'un isthme

 

S'il existe un pays O n'ayant qu'un voisin A, c'est qu'il est enclavé par A. Fusionnons pour l'instant les pays O et A en un unique pays A'. La carte devient coloriable (on a supprimé un pays). Reséparant A' en O et A, il suffit de donner à O (celui qui est enclavé) une couleur différente de celle de A pour obtenir un coloriage ne nécessitant pas plus de cinq couleurs. Notons que cet argument resterait inchangé si l'on était en train de démontrer le théorème des quatre couleurs.

S'il existe un pays O possédant deux voisins A et B, fusionnons-le avec l'un des deux, A par exemple. Colorions la nouvelle carte, puis reséparons O et A. Il suffit de donner à O une couleur différente de celle de A et B pour obtenir un coloriage ne nécessitant pas plus de cinq couleurs. Le même raisonnement conduit à la conclusion lorsque O possède trois voisins, et l'on peut noter, comme ci-dessus, qu'il reste valable dans la démonstration du théorème des quatre couleurs.

Lorsque O possède quatre voisins, le raisonnement ci-dessus fonctionne encore si l'on se contente de démontrer le théorème des cinq couleurs, mais il ne permet plus de conclure si l'on se limite à quatre couleurs. En effet, si ses quatre voisins sont coloriés différemment, une cinquième couleur sera nécessaire pour O. Dans la perspective de la démonstration du ``théorème'' de Kempe, nous donnons ci-dessous un autre argument pour ce cas, argument qui permet d'obtenir un 4-coloriage même lorsque O possède quatre voisins.

La procédure de réduction, dans ce cas, est analogue à celle employée ci-dessus, mais elle implique la fusion non plus de deux mais de trois pays, et s'appuie sur le fait que cinq pays ne peuvent être mutuellement frontaliers. Puisque ce résultat ``topologique'' nous est d'une grande utilité, nous en donnons un énoncé indépendant :

Lemme - Si un pays O possède quatre voisins ou plus, au moins deux d'entre eux ne sont pas frontaliers.

Supposons que O possède quatre voisins A, B, C et D, avec A et C non frontaliers. Fusionnons les trois pays O, A et C en un seul et colorions la nouvelle carte avec un maximum de cinq (ou de quatre) couleurs. Reséparons à présent O, A et C. On obtient un coloriage ne nécessitant pas plus de cinq (ou de quatre) couleurs en laissant à A et C leur couleur initiale (c'est possible puisqu'ils ne sont pas frontaliers) et en coloriant O avec une couleur différente de celles de B, D et A C.

 

Réduction par fusion de O, A et C (cas de quatre voisins)

 

Si, enfin, O possède cinq voisins A, B, C, D et E, il en existe encore au moins deux qui ne sont pas frontaliers. On peut recommencer la réduction ci-dessus. Elle nous permet de colorier tous les pays entourant O avec un maximum de 4 couleurs, et on utilise la cinquième pour colorier O.

 

Réduction par fusion de O, A et C (cas de cinq voisins)

 

La démonstration erronée de Kempe se fonde elle aussi sur l'étude des cinq cas considérés dans la preuve du théorème des cinq couleurs. Ses arguments pour traiter les quatre premières configurations sont ceux donnés ci-dessus. Dans le cas où O possède cinq voisins, le principe de la démonstration consiste à modifier le coloriage d'une carte plus petite, de manière à rendre possible le prolongement à O de ce coloriage, ceci sans nécessiter une couleur supplémentaire. Le raisonnement est le suivant : numérotant les couleurs de 1 à 4, on peut toujours se ramener à la figure ci-dessous, dans laquelle, les quatre couleurs étant utilisées (sans quoi le prolongement est évident), l'une d'elles l'est deux fois, par deux pays non frontaliers A et C.

 

Le voisinage d'un sommet de degré 5

 

Notre première tentative consiste à changer la couleur de B de 2 en 4. Ceci nous oblige à changer, pour tous les voisins de B de couleur 4, ce 4 en 2. Puis pour tous les voisins des voisins de couleur 2, ce 2 en 4 et ainsi de suite. Cette procédure s'arrête forcément puisque dans le pire des cas, on échange les couleurs 2 et 4 pour tous les pays de la carte qui sont de l'une de ces deux couleurs. Imaginons néanmoins que le pire ne se produit pas, et plus particulièrement que nous n'avons pas été obligés de modifier la couleur de E. Cela veut dire que nous avons encore un ``bon'' coloriage de la carte, dans lequel cette fois les voisins de O n'utilisent que les couleurs 1, 4 et 3, ce qui permet de colorier O avec 2. Si ceci n'est pas possible, on peut essayer de procéder de même en changeant la couleur de B de 2 en 3 et en espérant, cette fois, que la liste des pays affectés par l'échange 2/3 ne contiendra pas D.

Si ces deux modifications sont impossibles, c'est qu'il existe, d'une part une chaîne continue, formée de pays colorés alternativement en 2 et 4 et passant de B à E, d'autre part une autre chaîne continue, constituée elle de pays colorés en 2 et 3 et passant de B à D. Mais à cause de la première chaîne, il n'existe aucun moyen de passer du pays A au pays D par une chaîne continue de pays colorés en 1 ou 3 (car ces deux chaînes se couperaient forcément en un pays coloré à la fois en 2 ou 4 et en 1 ou 3). On peut donc, comme ci-dessus pour B, échanger la couleur de A de 1 en 3. De la même manière aucune chaîne continue formée de pays de couleur 1 ou 4 ne peut relier C à E, car il lui faudrait traverser la chaîne BD, avec là encore une incompatibilité de couleurs. Il est donc possible, par une nouvelle suite d'échanges, de recolorer C de 1 en 4. Finalement, dans le nouveau coloriage aucun voisin de O ne porte la couleur 1, il est possible de colorier O en 1 et le théorème est démontré.

Voilà qui paraît bien convaincant... Et qui pourrait, à tout le moins, faire douter ceux pour qui la preuve du théorème par ordinateur est sans véritable valeur car invérifiable. N'oublions pas que dans le cas présent il a quand même fallu onze ans pour déceler la faille dans le raisonnement...