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

 

B - L'historique du problème des quatre couleurs. Le domaine de validité du théorème

Selon certains auteurs, la possibilité de colorier avec quatre couleurs les cartes de géographie aurait été connue par les cartographes du moyen-âge. S'il faut en croire, au contraire, les affirmations d'Oysten Ore dans son livre, The Four-Color Problem paru en 1967 et dans lequel il faisait le point sur l'état de la science, rien n'atteste une telle connaissance, ni même un souci particulier d'``économiser'' le nombre de couleurs utilisées. A ce propos, on peut remarquer tout de suite que certaines conventions géographiques peuvent rendre faux le théorème en ce qui concerne le coloriage des cartes réelles. L'une de ces conventions est l'utilisation d'une même couleur, le bleu, pour représenter toutes les surfaces immergées telles que lacs, mers ou océans. Tenant compte de cette contrainte supplémentaire, on constate sans difficulté que la carte suivante n'est pas 4-coloriable (nous dirons qu'une carte est n-coloriable lorsqu'il existe un coloriage de cette carte n'utilisant pas plus de n couleurs).

 

Obstruction marine...

 

Dans un ordre d'idées voisin, un autre obstacle au coloriage ``économique'' peut être l'existence de régions enclavées. Par exemple, le département du Vaucluse est constitué de deux parties disjointes (deux ``composantes connexes'') dont l'une est entièrement limitée par la Drôme. Dans la mesure où la Drôme et le Vaucluse sont par ailleurs des départements limitrophes, il n'en résulte pas d'augmentation du nombre de couleurs nécessaires. Mais l'existence de Gibraltar empêche par exemple, si l'on veut que le coloriage rende compte des frontières politiques, de colorer l'Espagne et l'Angleterre de la même manière. Il existe, dans ce cadre plus ``réaliste'', un théorème, d'ailleurs plus simple à démontrer, qui affirme le fait suivant : si chaque région à colorer est constituée de 1 ou 2 morceaux (ce qui est loin d'être le cas des milliers de lacs, mers et océans constituant la zone immergée de la Terre...), il est toujours possible d'aboutir avec 12 couleurs, et certaines cartes requièrent effectivement les 12 couleurs. Ce résultat est dû à John Heawood, l'un des auteurs les plus prolifiques sur le théorème des quatre couleurs, et l'un des noms que nous verrons reparaître dans la suite de cet exposé.

La première trace écrite concernant le problème remonte au 23 octobre 1852 ; il s'agit d'une lettre d'Augustus de Morgan, professeur de mathématiques à University College (Londres) à Sir William Rowan Hamilton, professeur au Trinity College (Dublin).

''Un de mes étudiants m'a demandé aujourd'hui de lui donner une justification pour une propriété dont il ignorait, et ignore encore, s'il s'agit d'un fait connu. Il dit que si une figure est divisée de quelque manière que ce soit, et si on colorie les morceaux de telle sorte que, chaque fois qu'ils ont une ligne frontalière, leurs couleurs soient distinctes, il peut falloir quatre couleurs mais pas plus. Question : peut-on imaginer une figure nécessitant une cinquième couleur? Tout ce que je puis dire pour l'instant est la chose suivante : si quatre régions ont deux à deux une ligne frontalière, trois d'entre elles enclavent la quatrième et empêchent n'importe quelle cinquième de la toucher. Si ceci était vrai, quatre couleurs seraient toujours suffisantes...''

Nous verrons que cette dernière affirmation, dont la démonstration constitue par ailleurs la seule vraie contribution de de Morgan au problème des quatre couleurs, repose sur une assez grossière erreur de raisonnement. Quant à Hamilton, obsédé qu'il était alors par son invention des quaternions, il répondit à de Morgan :

''Il est peu probable que je regarde bientôt votre problème de ''quaternion'' de couleurs''...

Puis l'affaire en resta là jusqu'à ce que, en 1878, Arthur Cayley découvre à son tour le problème et lui donne une existence officielle en le posant à la communauté scientifique, dans deux notes parues l'une à la Société Mathématique de Londres, l'autre à la Société Géographique. Quant à l'étudiant de de Morgan qui avait découvert la propriété, son identité ne fut révélée qu'en 1880, grâce à une note du physicien Frederick Guthrie aux Proceedings of the Royal Society of Edinburgh :

''Il y a environ 30 ans, alors que je suivais les cours du professeur de Morgan, mon frère, Francis Guthrie, qui venait d'en sortir (et qui est maintenant professeur de mathématiques à l'Université Sud-Africaine, au Cap), me fit remarquer que le plus grand nombre de couleurs nécessaires au coloriage d'une carte en évitant de colorier pareillement deux régions linéairement frontalières est quatre. Il ne serait guère sérieux, après si longtemps, de tenter de restituer ici sa démonstration, mais la figure cruciale était la suivante :

 

Figure cruciale

 

Avec la permission de mon frère, je soumis le théorème au professeur de Morgan, qui eut beaucoup de plaisir à le lire et l'accepta comme un résultat nouveau.''

Francis Guthrie mourut en 1899, sans avoir jamais rien publié sur le théorème des quatre couleurs.

Peu après les articles de Cayley, un avocat anglais, Alfred Bray Kempe, publia une démonstration du théorème, puis en donna plusieurs améliorations qui parurent dans diverses revues. Ce travail le rendit célèbre et il obtint même une décoration. C'est seulement onze ans plus tard, en 1890, que John Heawood découvrit une erreur dans la preuve. Malgré de nombreuses contributions au problème du coloriage - et notamment son extension à des cartes dessinées sur des surfaces autres que la sphère -, la renommée de Heawood n'égala jamais celle de Kempe, et s'il finit aussi par obtenir une décoration, ce fut pour la restauration d'un château.

Tout n'était pas perdu, néanmoins, dans le travail de Kempe, et l'adaptation de ses idées permet déjà de démontrer un remarquable théorème des cinq couleurs (nous verrons qu'il est très facile de prouver un ''théorème des six couleurs'', en utilisant la remarque de de Morgan sur l'impossibilité de construire cinq pays mutuellement frontaliers). Utilisant le langage et les méthodes plus adaptées de la théorie des graphes, les chercheurs du XXème siècle apportèrent diverses améliorations, ce, notamment, en augmentant peu à peu le nombre minimal de pays que devait contenir un contre-exemple à la conjecture des quatre couleurs. Lors de la parution du livre de Ore mentionné ci-dessus, le record était arrivé à trente-six. En d'autres termes, on savait alors que toute carte ne contenant pas plus de 35 pays était coloriable avec quatre couleurs. La démonstration de ce résultat dans le livre occupe une dizaine de pages et repose sur d'assez nombreux pré-requis (ce qui n'est pas particulièrement énorme pour ce genre de démonstration, surtout dans un cadre très énumératif comme celui qui nous intéresse ici). Elle consiste, pour l'essentiel, à prouver qu'une carte n'excédant pas 35 pays doit nécessairement contenir l'une ou l'autre d'un certain nombre de configurations bien précises et qu'aucune de celle-ci ne peut être un ''contre-exemple minimal'' à la conjecture (c'est-à-dire tel que toute configuration strictement plus petite soit 4-coloriable). Un raisonnement par l'absurde simple permet alors de conclure.

A côté de ces recherches ''académiques'' furent proposées de nombreuses ''démonstrations'', ce par des amateurs comme par des professionnels, démonstrations écrites, la plupart du temps, dans une langue peu compréhensible et par conséquent difficiles à vérifier, mais en fin de compte, invariablement erronées. Ce jusqu'en 1971, où l'on crut sérieusement que le japonais Matsumoto, grâce au traitement informatique de milliers de cas, avait abouti. Ce ne fut, cette fois encore, qu'une fausse alerte, mais c'est dans la même veine qu'est taillée la preuve d'Appel et Haken.