QUATRE COULEURS PROBLÈME DES

L'irréductibilité de v₅ et ses conséquences

Kempe crut pouvoir réduire sa dernière configuration (le département ayant cinq voisins, ou, dans le langage dual que nous adoptons, v₅) en appliquant deux fois, simultanément, son argument au circuit séparateur C₅. Il fallut onze ans pour que P. J. Heawood (1890) prouvât l'illégitimité de cette double modification, en signalant de plus que l'argument de Kempe suffisait à démontrer le théorème des cinq couleurs, résultat plus faible (tout graphe planaire sans boucles est coloriable avec cinq couleurs).

La théorie des réductions, étudiée systématiquement par de nombreux auteurs (le travail fondamental a été accompli en particulier par H. Heesch), n'est pas encore achevée. On ne possède aucun critère général pour la réductibilité d'une configuration. Néanmoins, l'usage des réductions sur une échelle gigantesque a permis à Appel et Haken de contourner l'obstacle posé par l'irréductibilité de v₅ et de triompher du problème.

Près de cinq cents pages de raisonnements, dix mille diagrammes analysés, douze cents heures de calcul sur des ordinateurs de haute performance, dix milliards de décisions logiques élémentaires : tel est le bilan, dressé par les auteurs, des moyens mis en jeu. Dans l'ensemble inévitable de configurations, v₅ a fait place à 1 405 configurations dont la réductibilité a pu être prouvée par l'ordinateur – ou plutôt par trois ordinateurs de performances différentes.