Le Théorème des quatre couleurs

Le Théorème des 4 couleurs est une démonstration mathématique. Ce fut un énoncé abordé par les plus grands mathématiciens et le seul a être résolu à l'aide de l'ordinateur.

Le théorème des 4 couleurs a été inventé par le mathématicien anglais Augustus De Morgan, suite à la venu de Francis Guthrie, professeur de mathématiques et de son frère.

Ces derniers lui ont demandés si, pour colorer une carte de géographie en évitant d'affecter la même couleur à deux pays partageant une ligne de frontière commune, quatre couleurs suffisent. Attirés par la curiosité, plusieurs mathématiciens l'ont étudiés tels que Sir William Rowan Hamilton ou encore Arthur Kempe, en 1879, qui annonce avoir résolu la démonstration.

Mais onze ans plus tard (1890), Heawood troucve une faille dans la résolution de la démonstration de Kempe. Celui-ci évoque un théorème des 5 couleurs, il montre alors que l'on peut colorier une carte avec cinq couleurs, ses résultats s'avère plus facile à démontrer. En 1967 et 1971, Heesch se rend aux Etats-Unis afin de trouver une méthode de résolutions dans de meilleures conditions. Le pays étant équipé d'ordinateur plus puissant, le mathématicien allemand fait équipe avec ses confrères Haken et Shimamoto. Mais à un moment crucial des recherches, le financement est annulé.

Ce fut finalement en 1976 après 124 ans de recherche et 1200 heures de calcul pour nombre minimum de couleurs pour colorier une carte, Haken et  Kenneth Appel qui démontrent par informatique la conjecture de ce théorème avec plusieurs configurations. Robertson, Sanders, Seymour et Thomas simplifient leur algorithme, ce qui réduit les configurations de 1478 à 633.

Enfin, en 2005, Georges Gonthier proposera une preuve formelle à l'aide d'un assistant de preuve et le programme d'écriture et de vérification des preuves Coq ( logiciel mathématiques ). Quant à une preuve vérifiable à la main, elle reste à apporter.

Exemple de carte appliquant le théorème des quatre couleurs :

france4Couleurs.jpg

Sarah Pothier & Laurie Lescure