Théorème des quatre couleurs.

-

La pensée et ses outils > Philosophie > Logique et théorie de la connaissance > Mathématiques

Théorème des quatre couleurs

Selon le théorème des quatre couleurs :

« Toute carte plane peut être coloriée avec au plus quatre couleurs de manière à ce que deux régions adjacentes (c'est-à-dire partageant une frontière commune) ne partagent pas la même couleur. »

Le théorème des quatre couleurs a été initialement conjecturé en 1852 par Francis Guthrie, un étudiant de mathématiques, alors qu'il essayait de colorier une carte de manière qu'aucunes deux régions adjacentes n'aient la même couleur. La conjecture a été communiquée à Augustus De Morgan, qui l'a ensuite popularisée. De nombreuses tentatives pour prouver ou réfuter la conjecture ont été faites au cours des décennies suivantes. Alors que le théorème des cinq couleurs affirmant que cinq couleurs suffisent toujours pour colorier une carte plane a été relativement simple à démontrer. Celui des quatre a résisté très longtemps. En 1879, Alfred Kempe a publié une preuve qui a été acceptée pendant 11 ans jusqu'à ce que Percy Heawood trouve une erreur en 1890. Malgré cela, Kempe a introduit des idées et des méthodes (notamment les chaînes de Kempe) qui sont encore utiles dans la théorie des graphes aujourd'hui.

La première preuve correcte du théorème des quatre couleurs a été donnée par Kenneth Appel et Wolfgang Haken en 1976. Leur preuve a été révolutionnaire car elle a été la première à utiliser un ordinateur pour vérifier de nombreux cas individuels. Cette méthode a initialement suscité des controverses, car certains mathématiciens étaient sceptiques quant à l'utilisation d'un ordinateur pour prouver un théorème. La preuve d'Appel et Haken repose sur deux étapes principales :

• Ils ont montré qu'il suffisait de vérifier un ensemble fini mais très grand de configurations spécifiques de régions, appelé un « réducteur ».
• Ils ont ensuite utilisé un ordinateur pour vérifier ces configurations, confirmant qu'aucune d'entre elles ne nécessitait plus de quatre couleurs.

Le théorème des quatre couleurs est important parce qu'il a stimulé de nombreuses recherches en théorie des graphes et en combinatoire, et a conduit au développement de nouvelles techniques et approches. Il a aussi marqué un tournant dans l'acceptation des preuves assistées par ordinateur dans les mathématiques. Aujourd'hui, les preuves par ordinateur sont devenues courantes dans divers domaines mathématiques. De plus, bien que principalement théorique, le théorème des quatre couleurs a des applications pratiques en cartographie, en planification de réseaux et en optimisation.

Le théorème ne s'applique qu'aux cartes planes. Pour des surfaces plus complexes, comme des cartes sur des tores, le nombre de couleurs nécessaires peut être différent.

Dictionnaire Idées et méthodes