Le problème des quatre couleurs 121
1976
Appel et Haken prouvent le résultat
général au moyen d’une preuve trouvée
par ordinateur.
1994
La preuve par ordinateur est simplifiée
mais reste une preuve trouvée par
ordinateur.
Comme la couleur de départ n’a pas d’importance, nous prendrons
du bleu pour le Nevada et du vert pour l’Idaho. Jusque-là, tout
va bien. Ce choix oblige à colorier l’Utah en rouge, l’Arizona
en vert, la Californie en rouge, et l’Oregon en vert. Autrement
dit, l’Oregon et l’Idaho sont tous les deux coloriés en vert et ne
peuvent donc pas être différenciés. Mais si l’on disposait d’une
couleur supplémentaire, par exemple du jaune, nous pourrions
l’utiliser pour colorier l’Oregon et tout irait bien. Ces quatre
couleurs, le bleu, le vert, le rouge, et le jaune, seraient-elles suffisantes pour colorier n’importe quelle carte ? C’est ce que l’on
appelle le problème des quatre couleurs.
La propagation du problème Dans les vingt années qui
ont suivi la modélisation de ce problème par De Morgan qui en
comprit toute la portée, il commença à se répandre dans la communauté mathématique européenne et américaine. Dans les années 1860,
Charles Sanders Peirce, mathématicien et philosophe américain, pensait en avoir trouvé une preuve mais il ne reste aucune trace de son
raisonnement.
Le problème prit davantage d’importance encore au xix
e siècle grâce
à l’intervention de l’homme de science britannique Francis Galton. Voyant là un
moyen de promouvoir la science, il usa de persuasion pour convaincre l’éminent
mathématicien de Cambridge Arthur Cayley d’écrire un article sur le sujet en 1878.
Malheureusement, Cayley fut contraint d’admettre qu’il n’avait pas réussi à obtenir
une preuve mais observa qu’il suffisait de considérer les cartes cubiques uniquement
(celles où trois pays exactement se rejoignent en un point). Cette contribution
incita son étudiant Alfred Bray Kempe à chercher une solution. Pas plus d’un an
plus tard, Kempe annonça avoir trouvé une preuve. Cayley le félicita chaleureusement, la preuve fut publiée, ce qui valut à Kempe son admission à la Royal Society
de Londres.
Que se passa-t-il ensuite ? La preuve de Kempe était longue et techniquement très difficile à démontrer, et même s’il restait quelques sceptiques, elle fut
généralement acceptée. Mais dix ans plus tard, surprise, Percy Heawood, de l’université de Durham, trouva un exemple de carte qui révélait une faille dans le raisonnement de Kempe. Il ne parvint pas à en apporter la preuve, mais Heawood montra
toutefois que le problème des quatre couleurs n’était toujours pas résolu. Les mathématiciens n’avaient plus qu’à revenir à la planche à dessin et c’était aussi l’occasion
pour quelque petit nouveau de se faire un nom. Utilisant certaines des techniques
employées par Kempe, Heawood prouva un théorème des cinq couleurs selon lequel
Les États de l’ouest
américain
Arizona
C a l i f o r n i e
Nevada
Idaho
Utah
Oregon
1976
Appel et Haken prouvent le résultat
général au moyen d’une preuve trouvée
par ordinateur.
1994
La preuve par ordinateur est simplifiée
mais reste une preuve trouvée par
ordinateur.
Comme la couleur de départ n’a pas d’importance, nous prendrons
du bleu pour le Nevada et du vert pour l’Idaho. Jusque-là, tout
va bien. Ce choix oblige à colorier l’Utah en rouge, l’Arizona
en vert, la Californie en rouge, et l’Oregon en vert. Autrement
dit, l’Oregon et l’Idaho sont tous les deux coloriés en vert et ne
peuvent donc pas être différenciés. Mais si l’on disposait d’une
couleur supplémentaire, par exemple du jaune, nous pourrions
l’utiliser pour colorier l’Oregon et tout irait bien. Ces quatre
couleurs, le bleu, le vert, le rouge, et le jaune, seraient-elles suffisantes pour colorier n’importe quelle carte ? C’est ce que l’on
appelle le problème des quatre couleurs.
La propagation du problème Dans les vingt années qui
ont suivi la modélisation de ce problème par De Morgan qui en
comprit toute la portée, il commença à se répandre dans la communauté mathématique européenne et américaine. Dans les années 1860,
Charles Sanders Peirce, mathématicien et philosophe américain, pensait en avoir trouvé une preuve mais il ne reste aucune trace de son
raisonnement.
Le problème prit davantage d’importance encore au xix
e siècle grâce
à l’intervention de l’homme de science britannique Francis Galton. Voyant là un
moyen de promouvoir la science, il usa de persuasion pour convaincre l’éminent
mathématicien de Cambridge Arthur Cayley d’écrire un article sur le sujet en 1878.
Malheureusement, Cayley fut contraint d’admettre qu’il n’avait pas réussi à obtenir
une preuve mais observa qu’il suffisait de considérer les cartes cubiques uniquement
(celles où trois pays exactement se rejoignent en un point). Cette contribution
incita son étudiant Alfred Bray Kempe à chercher une solution. Pas plus d’un an
plus tard, Kempe annonça avoir trouvé une preuve. Cayley le félicita chaleureusement, la preuve fut publiée, ce qui valut à Kempe son admission à la Royal Society
de Londres.
Que se passa-t-il ensuite ? La preuve de Kempe était longue et techniquement très difficile à démontrer, et même s’il restait quelques sceptiques, elle fut
généralement acceptée. Mais dix ans plus tard, surprise, Percy Heawood, de l’université de Durham, trouva un exemple de carte qui révélait une faille dans le raisonnement de Kempe. Il ne parvint pas à en apporter la preuve, mais Heawood montra
toutefois que le problème des quatre couleurs n’était toujours pas résolu. Les mathématiciens n’avaient plus qu’à revenir à la planche à dessin et c’était aussi l’occasion
pour quelque petit nouveau de se faire un nom. Utilisant certaines des techniques
employées par Kempe, Heawood prouva un théorème des cinq couleurs selon lequel
Les États de l’ouest
américain
Arizona
C a l i f o r n i e
Nevada
Idaho
Utah
Oregon