Guthrie Francis

Imaginez une carte découpée en régions. On veut donner une couleur à chaque région pour que deux régions qui partagent une frontière aient des couleurs différentes. En 1852, Francis Guthrie remarque qu'une carte des comtés d'Angleterre peut être coloriée avec quatre couleurs seulement. Il se demande alors si ce nombre suffit pour toute carte plane finie et correctement définie, même très compliquée. Cette question devient le problème des quatre couleurs : elle porte sur les frontières communes, pas sur les régions qui se touchent seulement en un point.

Francis Guthrie est à l'origine d'une conjecture de théorie des cartes : toute carte finie, correctement définie et dessinée dans le plan peut être coloriée avec au plus quatre couleurs, de sorte que deux régions ayant une frontière commune portent des couleurs différentes. Une carte planaire est ici une carte que l'on peut dessiner sur une surface plane sans que ses frontières se croisent autrement qu'aux points et frontières prévus par le découpage. Deux régions qui se rencontrent seulement en un point n'imposent donc pas de couleurs différentes.

La proposition est une conjecture tant qu'elle n'est pas démontrée. Elle devient le théorème des quatre couleurs après la démonstration obtenue en 1976 par Wolfgang Haken et Kenneth Appel. Cette démonstration utilise un programme informatique pour effectuer une vérification exhaustive de cas. Pour les cartes finies correctement définies du cadre planaire, le résultat concerne le nombre maximal de couleurs nécessaires : certaines cartes peuvent être coloriées avec moins de quatre couleurs. Guthrie, mathématicien et botaniste, avait formulé la question en coloriant une carte des comtés d'Angleterre en 1852.

Considérons une carte plane abstraite composée de quatre régions : une région centrale A, une région à gauche B, une région à droite C et une région en bas D. Les frontières communes sont A–B, A–C et A–D. Les contacts en un seul point ne comptent pas.

Données : les régions sont A, B, C et D ; la liste des frontières communes est A–B, A–C et A–D.
1. La région A reçoit le rouge.
2. B partage une frontière avec A : B reçoit le jaune.
3. C partage une frontière avec A : C reçoit le noir.
4. D partage une frontière avec A, mais pas avec B ni C : D reçoit le jaune.

La coloration utilise donc trois couleurs, rouge, jaune et noir, et respecte chaque frontière commune. Le contrôle consiste à relire les trois paires : A–B, A–C et A–D ont bien des couleurs différentes. Les paires B–D et C–D peuvent partager une couleur, puisqu'elles ne figurent pas parmi les frontières communes.

Pour colorier une carte, on commence par relever les régions qui partagent réellement une frontière. On attribue ensuite des couleurs en vérifiant chaque voisin déjà colorié. Deux régions qui se touchent seulement par un sommet peuvent conserver la même couleur.

Dans un exercice de combinatoire, on peut construire le graphe dual d'une carte finie correctement définie : chaque région devient un sommet et chaque frontière commune devient une arête. Cette représentation est utile lorsque le dessin est chargé, car elle rend la contrainte de voisinage explicite ; selon la carte, le dual peut comporter des boucles ou des arêtes multiples, et il ne faut donc pas lui imposer implicitement la structure d'un graphe simple.

Pour une carte donnée, le geste consiste à chercher une coloration valide, pas nécessairement à utiliser quatre couleurs. Si trois couleurs suffisent, elles répondent déjà au besoin ; le théorème garantit seulement que quatre couleurs sont toujours suffisantes dans le cadre planaire.

La conjecture des quatre couleurs et le théorème des quatre couleurs désignent la même question, mais pas le même statut. Une proposition encore à démontrer est une conjecture ; après la démonstration de 1976 par Wolfgang Haken et Kenneth Appel, on parle de théorème. Une carte qui satisfait déjà une coloration ne constitue donc pas, à elle seule, une preuve de la proposition générale.

La coloration de régions ne se confond pas avec la coloration de sommets d'un graphe quelconque. Pour les cartes, les voisins sont les régions qui partagent une frontière commune, et la représentation pertinente est planaire. Si le problème porte sur des sommets reliés par des arêtes sans venir d'un découpage planaire, il faut appliquer le résultat adapté à ce graphe, pas invoquer automatiquement quatre couleurs.

Le nombre quatre est une borne supérieure, non une obligation. Une carte à une, deux ou trois régions peut nécessiter moins de quatre couleurs ; l'observation correcte est alors le nombre minimal nécessaire pour cette carte.

Le mot « voisine » peut tromper. Deux régions qui se touchent seulement en un point ne partagent pas une frontière commune au sens du problème. Le symptôme est une couleur jugée interdite alors qu'aucun segment de frontière ne sépare les deux régions : il faut examiner la nature du contact avant d'ajouter une couleur.

La conclusion porte sur les cartes planaires. Une carte dessinée sur une autre surface, ou un réseau dont les croisements ne peuvent pas être éliminés, n'entre pas automatiquement dans ce cadre. Il faut d'abord vérifier que le modèle est bien celui d'une carte planaire.

Le théorème des quatre couleurs prolonge directement la question posée par Guthrie : le lecteur y gagne la formulation du résultat démontré, séparée de l'épisode historique qui l'a fait naître.

Le graphe planaire fournit le langage structurel de la coloration des cartes : le lecteur y gagne une manière de représenter les régions et leurs frontières par des sommets et des arêtes.