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

 

C - L'énoncé du problème en théorie des graphes. Graphes planaires et identité d'Euler

La théorie des graphes fournit une manière commode d'associer à toute carte de géographie un objet abstrait plus simple à représenter et à manipuler, son graphe d'incidence, graphe sur lequel les propriétés de coloriage ont en outre une traduction simple.

Un graphe abstrait est un ensemble de sommets (qui peut être fini ou non suivant les auteurs ; dans le cadre de cet exposé, il sera toujours fini puisque les sommets seront associés aux régions de la carte) et d'arêtes reliant certains de ces sommets. En général, il peut y avoir plusieurs arêtes reliant un même couple de sommets, il peut même y avoir des boucles (arêtes ayant même origine et extrémité). Ceci, néanmoins, ne se produira jamais pour un graphe d'incidence (on dit qu'un tel graphe est simple). Si s est un sommet du graphe G, le nombre d'arêtes qui partent de s est appelé le degré de s et noté d(s). Cette notion reviendra souvent dans nos raisonnements.

A toute carte de géographie, on associe son graphe d'incidence de la manière suivante :

A chaque pays est associé un sommet ;

Deux sommets sont reliés par une arête si les pays correspondants partagent une ligne frontière (non réduite à un point).

 

Le graphe d'incidence d'une carte

 

(les sommets correspondant aux pays A et B ne sont pas reliés car la frontière entre ces pays se réduit à un point. Il en est de même pour C et D).

On constate que tout graphe d'incidence est un graphe planaire : cela signifie qu'il est possible de dessiner, dans le plan, une représentation concrète du graphe dans laquelle les traits figurant les arêtes ne se coupent pas - sauf évidemment en un éventuel sommet commun. Dans le cadre de la théorie des graphes, le théorème des quatre couleurs devient :

Théorème - Pour tout graphe planaire G, il existe une manière de colorier ses sommets telle que deux sommets adjacents (id est : reliés par une arête) soient colorés différemment.

A propos des graphes planaires, quelques remarques nous éclaireront mieux. Tout d'abord, tout graphe fini peut être dessiné dans l'espace 3 de telle sorte que deux arêtes ne se coupent qu'en leur éventuel sommet commun (on dit alors qu'on a plongé le graphe dans 3). Il suffit pour cela de représenter les sommets sur l'axe vertical (Oz), de dessiner autant de demi-plans distincts contenant (Oz) qu'il y a d'arêtes et de représenter, dans chacun de ces demi-plans, une arête par un demi-cercle (imaginer les pages d'un livre tournant autour de la tranche, chaque page contenant le dessin d'une arête).

 

Plongement spatial d'un graphe

 

Avec un peu plus de soin quant à la localisation des sommets, on n'a pas de mal à trouver un dessin où, de plus, les arêtes sont rectilignes (à condition, évidemment, que le graphe représenté soit simple, c'est-à-dire sans boucle ni arêtes multiples). On peut donc dire que tout graphe fini est ''spatial'', c'est-à-dire plongeable dans 3. En revanche, il existe des graphes finis qui ne sont pas planaires. Les plus connus sont les suivants :

 

Les graphes K33 (à gauche) et K5

 

Un remarquable théorème, démontré en 1930 par le mathématicien polonais Kuratowski, prouve que les deux graphes K33 et K5 ci-dessus sont essentiellement les deux ``seuls graphes non-planaires'', au sens où tout graphe non planaire contient un sous-graphe homéomorphe à l'un d'entre eux, c'est-à-dire se réduisant à l'un d'eux après l'effacement d'un certain nombre de sommets de degré 2 (sommets parasites sur les arêtes que l'on peut supprimer sans rien changer à la topographie de la figure). Mais si la preuve du théorème de Kuratowski requiert un nombre assez important d'outils, la démonstration de la non-planarité des graphes K33 et K5 est, quant à elle, une conséquence simple de l'identité d'Euler. Celle-ci affirme que, lorsqu'on dessine un graphe connexe (c'est-à-dire dans lequel deux sommets quelconques peuvent être reliés par une suite d'arêtes) dans le plan,

S désigne le nombre de sommets du graphe, A le nombre d'arêtes et F le nombre de faces du dessin, c'est-à-dire de régions du plan délimitées par les arêtes (les composantes connexes du complémentaire du dessin), y compris la ``face extérieure'', la seule de toutes à ne pas être bornée.

Démonstration de l'égalité d'Euler

Soit n le nombre d'arêtes du graphe. Nous raisonnons par récurrence sur n. Si n=0, le graphe ne comprend qu'un sommet à cause de la connexité, il n'y a aussi qu'une face et le résultat est évident.

Supposons le résultat vrai pour tout graphe possédant au maximum n arêtes et soit G un graphe connexe à n+1 arêtes. Supprimons de G une arête quelconque et considérons deux cas. Soit l'arête supprimée était bordée par deux faces distinctes, soit elle était bordée par la même face. Dans le premier cas, le nouveau graphe obtenu reste connexe : il suffit de voir que les deux extrémités de l'arête supprimée peuvent encore être reliées malgré la disparition de celle-ci. Or, parmi les deux faces qui bordent cette arête, une au moins est bornée, donc entièrement entourée par des arêtes. On passe donc de s1 à s2 en faisant ``le grand tour'', comme l'indique le dessin ci-dessous:

 

Le grand tour...

 

Dans ce cas la suppression de l'arête a donc supprimé également une face et laissé inchangé S-A+F. Dans le deuxième cas, après suppression de l'arête, la face qui la bordait des deux côtés entoure maintenant un sous-graphe et coupe G en deux graphes connexes G1 et G2. On a, avec des notations évidentes, S1-A1+F1=2 et S2-A2+F2=2. La relation pour G en résulte en additionnant ces deux égalités et en remarquant que A1+A2=A-1 (il manque l'arête que l'on a supprimé) et F1+F2=F+1 (la face qui entoure un des sous-graphes est aussi une face de l'autre).

Comme nous l'indiquions plus haut, la non-planarité des graphes K33 et K5 résulte simplement de l'égalité d'Euler. En effet, imaginons par exemple K33 dessiné dans le plan. Remarquons qu'aucune des faces du dessin ne pourrait être ``triangulaire''. En effet, une telle propriété signifierait qu'existe dans K33 un chemin fermé de longueur 3, ce qui est impossible puisque tout chemin de longueur impaire conduit d'une maison à une usine ou vice-versa ce qui l'empêche d'être fermé. Chaque face nécessite donc, pour la border, un minimum de 4 arêtes. Il en résulte que la somme (pour toutes les faces) des nombres d'arêtes bordant chaque face vaut au moins 4F. Mais par ailleurs, cette somme est au maximum égale à 2A (chaque arête apparaît, dans la somme, une fois ou deux suivant qu'elle est bordée par des faces différentes ou par la même). De sorte que 2F A. Il résulte alors de l'égalité d'Euler que 4 = 2S-2A+2F 2S-2A+A d'où A 2S-4. Or, dans le cas du graphe K33, A=9 et 2S-4=12-4=8. La démonstration est analogue pour K5. Mais comme une représentation de celui-ci pourrait contenir des faces triangulaires, on trouve une inégalité un peu moins contraignante sur les arêtes et les sommets, A 3S-6, égalité qui suffit là encore à conclure.

Il résulte de la non-planarité du graphe K5 qu'il est impossible de trouver une carte de géographie dont le graphe d'incidence soit K5. Ceci justifie la remarque de de Morgan dans sa lettre à Hamilton, selon laquelle il n'arrive jamais que cinq pays soient mutuellement frontaliers. Malheureusement, cette remarque ne suffit pas à prouver, contrairement à ce qu'il semble tenir pour évident dans cette lettre, le théorème des quatre couleurs. Vu la véracité du dit théorème, nous ne pourrons évidemment pas donner de contre-exemple, mais on peut remarquer que dans l'exemple ci-dessous, quatre couleurs sont nécessaires, alors qu'il n'existe aucune configuration de quatre pays frontaliers.

 

Réfutation d'un argument simpliste

 

L'identité d'Euler possède une autre conséquence importante, qui fut le point de départ de la démonstration erronée de Kempe. Comme nous l'avons vu plus haut, dans un graphe planaire simple (sans boucle ni arête multiple : il en résulte que dans tout dessin du graphe, les faces sont bordées par au moins trois arêtes) possédant au moins quatre sommets, on a l'inégalité A 3S-6. Supposons que dans un tel graphe, tous les sommets soient de degré au moins égal à 6. Il en résulterait que la somme des degrés vaut au moins 6S. Or, dans cette somme chaque arête est comptée exactement 2 fois (elle contribue pour 1 dans le degré de ses deux extrémités) et on aurait 6S 2A, d'où A 3S, ce qui est absurde.

Théorème - Tout graphe planaire possède un sommet de degré inférieur ou égal à 5.