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

 

H - Ensembles inévitables : la méthode des charges

Nous avons vu que tout graphe d'incidence normal possède des faces triangulaires et des sommets de degré supérieur ou égal à 5. L'idée, pour engendrer un ensemble inévitable de configurations, est de considérer le graphe comme un réseau électrique en affectant à chaque sommet une charge initiale égale à 6 - d(s) (où d(s) désigne le degré de s). Un calcul élémentaire utilisant l'égalité d'Euler d'une part, d'autre part le fait que, puisque toutes les faces sont triangulaires, 3F = 2A et enfin la propriété analogue sur les sommets S d(s) = 2A (cette dernière propriété est connue comme une partie du ''lemme des poignées de mains" : celui-ci affirme que le nombre total de poignées de main échangées est égal à la moitié de la somme, prise sur tous les individus, des nombres de poignées de main données), montre que la somme des charges dans un graphe normal est égal à 12. Puisque les seuls sommets chargés positivement sont ceux de degré 5 dont la charge vaut 1, il en résulte notamment qu'aucune carte comptant moins de 12 pays ne peut conduire à un graphe d'incidence normal, donc à un contre-exemple minimal au théorème, qui est donc démontré élémentairement pour les cartes comptant jusqu'à 11 pays.

Imaginons maintenant que l'on déplace les charges électriques sur le réseau, par quantités fractionnaires le cas échéant. La charge totale restera égale à 12, mais certains sommets de degré 5 pourraient se trouvés déchargés, voire chargés négativement, pendant que des sommets de degré 6 ou plus se retrouveraient positifs. Le point crucial dans cette procédure est qu'il restera toujours, inévitablement, des sommets chargés positivement, et que les configurations correspondantes, dont la géométrie dépend évidemment de la procédure de déchargement choisie, formeront donc un ensemble inévitable. Supposons par exemple que la procédure choisie consiste à transférer 1/5 d'unité de charge de chaque sommet de degré 5 vers chacun des sommets voisins de degré 7 ou davantage. L'ensemble inévitable de configurations qui en résulte se réduit aux deux figures ci-dessous, dont aucune n'est irréductible.

 

Un exemple d'ensemble inévitable

 

La méthode des charges avait d'abord été imaginée par Heesch, qui n'alla cependant pas très loin dans cette direction. C'est pourtant cette idée qui permit à Appel et Haken de démontrer le théorème. Au début des années 1970, ceux-ci disposaient d'un nombre assez important de techniques de démonstration de réductibilité, mises au point notamment par Heesch et par Karl Dürre, un de ses élèves. En tête de ces outils, Haken et Appel développèrent la stratégie suivante : partir d'une procédure de transfert de charges d'aspect prometteur, tenter de prouver la réductibilité des configurations résultantes, et pour celles qui résistaient, redéplacer les charges pour essayer de se ramener à des configurations plus simples. Ce programme dura finalement quatre ans, dont un ultime assaut de près de six mois, et requit 1200 heures d'ordinateur. La procédure de déchargement finalement utilisée différait de celle dont ils étaient partis par 500 modifications suggérées par les résultats des calculs intermédiaires. Les deux mathématiciens étudièrent à la main plus de 10 000 voisinages de sommets chargés positivement, l'ordinateur eut à examiner près de 2000 configurations et à prouver la réductibilité de 1482.