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

 

I - Une généralisation du problème

Nous avons souligné plusieurs fois, dans ce qui précède, la contribution ''négative'' de John Heawood au théorème des quatre couleurs. Il ne faudrait pas croire, cependant, que l'essentiel de son apport à la question du coloriage des cartes ait consisté à démolir le raisonnement de Kempe et à le retailler pour démontrer le théorème des cinq couleurs.

Nous avons déjà mentionné son théorème indiquant la possibilité de colorier avec 12 couleurs - et parfois pas moins - les cartes dans lesquelles chaque pays possède au maximum deux composantes connexes. Nous ne pousserons pas plus loin ce genre de généralisation mais examinerons la contribution de Heawood à un autre aspect du problème, le coloriage des cartes de géographie non planaires.

Les cartes de géographie terrestres conduisent à des graphes d'incidence planaires. On pourrait aussi dessiner la carte directement sur une sphère (il s'agit même d'une approche assez riche de conséquences, si l'on en croit Christophe Colomb) et le graphe d'incidence correspondant serait ''sphérique'', c'est-à-dire plongeable dans la sphère. L'équivalence, en général, entre planarité et ''sphéricité'' d'un graphe est un exercice simple, le passage d'une représentation à l'autre s'effectuant au moyen de la projection stéréographique.

 

Correspondance entre graphes planaires et graphes sphériques

 

Généralisant cette remarque, on peut se demander si, de même que la sphère est le lieu naturel de représentation des graphes planaires, il existe, pour des graphes non planaires, des surfaces simples sur lesquelles il est possible de les dessiner. La réponse à cette question est oui et nous allons indiquer la procédure pour le graphe K33. Il est possible de représenter à plat, donc sur la sphère, toutes les arêtes de ce graphe sauf une. Pour dessiner la dernière sans couper de trait existant, il suffit de créer une petite anse sur la sphère qui nous permettra de passer, comme sur un pont, par dessus l'arête que nous aurions, sinon, été obligés de couper.

 

Le dessin de K33 sur un tore...

 

La surface obtenue en rajoutant cette anse peut être continûment déformée en un tore, et il en résulte que l'on peut plonger K33 dans un tore. Le même résultat est vrai pour K5. Plus généralement, tout graphe non planaire peut être dessiné sur un ''tore à n trous'' (n est, en gros, le nombre minimal d'intersections d'arêtes dans une représentation à plat du graphe). Le plus petit n pour lequel un tel dessin est possible est appelé le genre du graphe (c'est aussi le ''genre topologique'' du tore à n trous) et on montre alors une généralisation de l'identité d'Euler : si G est un graphe de genre n tracé sur un tore à n trous, le dessin découpe encore un certain nombre F de faces et l'on a

Le nombre c = 2 - 2n est appelé la ''caractéristique d'Euler-Poincaré'' du tore à n trous (il constitue un invariant topologique de cette surface). Par des raisonnements analogues à ceux faits plus hauts pour les graphes planaires, Heawood montra qu'un graphe de genre n possède toujours, lorsque c 0, un point s dont le degré vérifie

Il en déduisit, comme on démontrait plus haut le théorème des six couleurs, que tout graphe de genre n est coloriable avec un maximum de m0+1 couleurs, et émit la conjecture que ce nombre était le meilleur possible, c'est-à-dire qu'il existait, pour tout n, un graphe de genre n dont le coloriage nécessite m0+1 couleurs. Cette conjecture a été prouvée vers la fin des années 1960 par Ringel et Youngs. Dans le cas du tore, le nombre minimal de couleur est 7, et la figure ci-dessous donne un exemple de carte, dans un monde torique, constituée de sept pays mutuellement frontaliers.

 

Géographie venue d'ailleurs...

 

En guise de conclusion, signalons deux petits faits amusants : pour toutes les surfaces sauf la sphère, prouver la possibilité de colorier avec m0+1 couleurs est un exercice simple, et c'est prouver la minimalité de ce nombre m0+1 qui est difficile. C'est exactement le contraire qui se produit sur la sphère.

Par ailleurs, il est vraiment dommage que la démonstration de la formule de Heawood donnant m0+1 nécessite l'hypothèse c 0 puisque, lorsque c = 2, on trouve m0+1 = 4...