NOMBRES – Curiosités, Théorie et Usages Accueil DicoNombre Rubriques Nouveautés Édition du: 09/01/2024 Orientation générale  DicoMot Math Atlas Actualités M'écrire Barre de recherche DicoCulture Index alphabétique Références Brèves de Maths
	TOPOLOGIE
Débutants Géométrie	QUATRE COULEURS Divers				Glossaire Géométrie
INDEX Quatre couleurs Géométrie Topologie	Général	Historique	Prince de Möbius	Diamant de Birkhoff
		Sommaire de cette page >>> Origine (Gunthrie) >>> Premières démonstrations (Kempe) >>> Méthode de réduction (Heesch) >>> La démonstration (Appel)

Théorèmes des quatre couleurs

Ou problème de Gunthrie

Historique

Premier questionnement en 1852 à propos de la coloration des cantons anglais. Résolution en 1976 avec l'aide d'un ordinateur pour explorer systématiquement les 1500 cas récalcitrants.

Pour résoudre ce problème qui semblait simple, il a fallu attendre que la puissance de calcul des ordinateurs soit disponible.

Américain: The four color problem ot the 4-color theorem (4CT) or the Gunthrie's problem

Historique
Comme souvent pour les problèmes les plus ardus, la démonstration correspond à une succession de procédés permettant de reporter la démonstration générale dans un autre monde et, comme cela, de rebond en rebond, aboutir à la solution finale. Historique
/	/	Aucune trace de ce problème attestée avant 1840.
1750	Leonhard Euler (1717-1783)	Lettre à Goldbach mentionnant la relation relative aux polyèdres.
1794	Adrien-Marie Legendre (1752-1833)	Prouve la relation d'Euler.
1811	Simon-Antoine Lhuilier	La relation d'Euler s'applique aux polyèdres troués.
1813	Augustin Cauchy (1798-1857)	Montre que la relation d'Euler relative aux polyèdres est valable aussi pour les cartes de plus de deux régions et sans région incluse.
1840	August Möbius (1790-1868) Astronome Leipzig	Problème des cinq princes qui préfigure l'énoncé du problème des quatre couleurs. Ce problème montre l'impossibilité de partager le royaume en cinq régions mitoyennes entre elles.
1852	Francis Guthrie (1831-1899) Mathématicien et botaniste Anglais alors professeur à la South African University, Cape Town (Afrique du Sud)	Énonce le problème. Il remarque qu'il lui suffit de quatre couleurs pour colorer la carte chargée des cantons (counties) d'Angleterre. Les cantons ayant une frontière commune sont tous de couleurs différentes. Ancien élève de De Morgan, il lui communique la conjecture via son frère Frederick, alors encore lui aussi élève de De Morgan. Cette illustration était dans la marge de la correspondance entre lui et son frère.

1852	Auguste De Morgan (1806-1871) University College, Londres William Hamilton (1830-1803) Irlandais	De Morgan s'y intéresse, avoue qu'il n'a pas beaucoup progressé, et passe le bébé à Hamilton. Le 23 octobre 1852 ; lettre d'Augustus de Morgan, professeur de mathématiques à University College (Londres) à Sir William Rowan Hamilton, professeur au Trinity College (Dublin): "… Si quatre régions ont deux à deux une ligne frontalière, trois d'entre elles enclavent la quatrième et empêchent n'importe quelle cinquième de la toucher. Si ceci était vrai, quatre couleurs seraient toujours suffisantes…" Hamilton répond qu'il n'a guère le temps (l'envie) de s'intéresser à ce problème de quaternion de couleurs (I'm not likely to attempt your "quaternion" of colours very soon). Extrait de la lettre 23 octobre 1852 De Morgan laisse tout de même un théorème: Il est impossible de disposer cinq régions de telle façon qu'il existe des frontières communes entre tous les couples possibles. Propriété qui laisse penser que quatre couleurs devraient suffire.
1860	De Morgan William Whewell Philosophe	De Morgan écrit à ce philosophe sur le problème des quatre couleurs ainsi qu'à Robert Ellis. Whewell publie: The philosophy of discovery dans le magazine Athenaeum. De Morgan, en retour, publie la revue de cet article et se faisant, il est le premier à mentionner le problème des quatre couleurs dans un écrit public. Ainsi, le problème devint connu aux États-Unis. (…) Now, it must have been always known to map-colourers that four different colours are enough. (En fait, les cartogrpahes ont toujours su que quatre couleurs sont suffisantes).
1869	Charles Sanders Pierce Américian	Lui aussi alerté par De Morgan, passe une bonne part de sa vie sur ce problème et ne conçoit pas que les mathématiciens aient à passer autant de temps sur un problème aussi simple. Il aurait présenté une solution à HArvard qui n'a jamais été retrouvée dans ses manuscrits. Il s'intéresse également aux volumes et pense, par exemple, qu'il faut sept couleurs pour un tore.
1973	Carl Hierholzer (1840-1871)	La preuve du théorème d'Euler (nombre pair d'arêtes) fut en fait publiée par Hierholzer.
1878	Arthur Cayley (1821-1895)	Publie le problème des quatre couleurs dans les Proceedings of the London Mathematical Society. C'est la première référence écrite énonçant le problème et sollicitant une réponse.

1879	Alfred Kempe (1849-1922)	Publie une solution dans L'American Journal of Mathematics. Elle s'avère non valable pour quatre couleurs. Notamment dans le traitement de réduction des pentagones. Par contre: elle fera progresser la démonstration pour cinq couleurs, et elle contient la trame de la solution finale: les chaines de Kempe. >>> Théorème: dans toute carte, il existe au moins une région avec cinq voisines ou moins. La région est en forme de cercle, de triangle, de carré ou de pentagone.
1880	Peter Tait (1831-1901) et Julius Peterson	Le premier publie aussi une solution, réfutée par le second. (Tait est connu pour ses études sur la classification des nœuds). Il conjecture que les graphes hamiltoniens peuvent être colorés avec quatre couleurs. Contre-exemple trouvé en 1946 par William Tutte (1917-2002).
1885	Thomas Penyngton Kirkman	Spécialiste des polyèdres, il redémontre la relation d'Euler et il étudie les cycles (hamiltoniens) dans ces volumes.
1885	Richard Baltzer Géomètre allemand	Exhume l'énigme des cinq princes de Möbius. Il en déduit à tord, comme beaucoup d'autres à l'époque, que cela prouve que quatre couleurs sont suffisantes. Frederick Temple, évêque de Londres, fera la même confusion en 1889.
1886	/	Le problème est posé comme défi aux élèves du Clifton College.
1890 1891	Percy Heawood (1861-1955)	Découvre une erreur dans la démonstration de Kempe. Aménage la démonstration et établit le théorème des cinq couleurs. Détermine le nombre maximum de couleurs pour toutes les surfaces, sauf le plan (Conjecture). Il s'intéresse aussi aux surfaces non planes. Il conjecture une limite supérieure du nombre de couleurs en fonction du nombre de trous dans la surface.
1891	Lothar Heffter	Constate une erreur dans le raisonnement de Heawood sur les tores avec un ou deux trous.
1900?	Heinrich Tietze (1880-1964)	Établit un premier résultat sur les domaines adjacents d'une surface orientée. Démonstration du fait que le théorème des quatre couleurs n'a pas d'équivalent dans les dimensions supérieures à 2.
1904	Paul Wernicke Allemand	Démontre que toute carte doit contenir au moins l'une de ces cinq configurations inévitables: Un des premiers à établir des configurations inévitables de grande ampleur. Par exemple: le pentagone inévitable serait remplacé par un couple de pentagones adjacents et un pentagone adjacent à un hexagone, ce qui produit une configuration inévitable plus grande.
1913	George D. Birkhoff (1884-1944) Harvard	Il introduit la notion de configurations réductibles. Introduit les polynômes chromatiques qui s'avérèrent utiles mais pas pour le problème des quatre couleurs. Le diamant de Birkhoff est réductible
1922	Philip Franklin (1898-1965) MIT	Sur la base des travaux de Birhoff, développe le concept de configurations réductibles et démontre que la conjecture est vraie (quatre couleurs) pour toutes les cartes de moins de 26 couleurs: tout graphe planaire ayant au plus 25 sommets est 4-coloriable. 1926, Reynolds donne 27; 1940, Winn arrive à 35; 1970, Ore et Stemple à 39; et 1976, Mater atteint 95. Il donne un contre-exemple de la conjecture de Heawood avec un graphe cubique à 12 sommets.
1940	Henri Lebesque (1875-1941)	S'intéresse au problème: analyse le voisinage des pentagones et en donne la liste exhaustive À partir de la relation d'Euler, construit un nombre considérable de configurations inévitables.

Hermann Minkowski (1864-1909) prend ce problème de haut en prétendant que seuls des mathématiciens de troisième catégorie auraient étudié ce problème. Ce qui expliquerait qu'il ne soit pas encore résolu. Il entreprend son étude et reconnait quelque temps plus tard: "J'ai indisposé le ciel par mon arrogance: ma démonstration est, elle aussi, inexacte". (Heaven is angered by my arrogance; my proof is also defective).

1950 à 1970	Henrich Heesch (1906-1995) Hanovre Dürre (le programmeur) Jean Mayer Montpellier	Développe les ingrédients qui s'avéreront utiles à la preuve finale, notamment la notion de réduction. C'est lui qui passe à la représentation des cartes en graphes. Analogie des charges électriques pour réduire le nombre de cas inévitables (1969). Pense que 8 900 cas irréductibles sont à explorer. Il utilise pour cela les ordinateurs. Cependant des configurations (circuit) ayant 18 régions comme frontière apparaissent. Trop gigantesque pour être testées. Son ouvrage s'intitule: Untersuchungen zum Vierfarbenproblem.
1959	HSM Coxeter Géomètre	C'est lui qui donne la paternité du problème à Guthrie et non à Möbius Ce que personne ne conteste depuis.
1968	G. Ringel et E. Youngs	Démonstration de la conjecture d'Heawood: le nombre minimal de couleurs est égal à la limite de Heawood. Deux exceptions: la sphère et la bouteille de Klein.

1970	Wolfgang Haken (né en 1928)	Perfectionne la méthode des charges de Heesch. Pense que le problème est désormais à portée.
1976	Kenneth Appel (1932-2013) et Wolfgang Haken John Coke Programmeur	Démonstration finale par exploration systématique des cas particuliers (Université de l'Illinois). En effet, la démonstration résout les cas généraux en laissant de côté 1478 cas particuliers. Ils ont réussi à limiter les configurations maximales à 14 régions en frontières. Ce qui devenait accessible au calcul par ordinateurs. C'est la première démonstration mathématique assistée par ordinateur. Elle pose souci aux autres mathématiciens. La confirmation n'est pas aisée. Comment vérifier l'informatique sous-jacente? Est-ce que le programme réalisé est fiable ?
1995	Neil Robertson (né en 1938), Daniel Sanders, Paul Seymour (né en 1950) et Robin Thomas (né en 1962)	Simplification de la solution. Réduction des cas à tester à 633 au lieu de 1478. Ci-contre analyse de graphes utilisant la formule d'Euler et le calcul de charges.
2004	Georges Gonthier (Cambridge) et Benjamin Werner (INRIA-France)	Preuve formelle à l'aide d'un assistant de preuve (programme Coq). La preuve du théorème des quatre couleurs est définitivement admise par tous les mathématiciens. Voir Preuve concernant l'empilement des sphères
2005	J. Ferro	Disqualifie certaines prétendues preuves rapides du théorème. Reference 1: The four color theorem – MathWorld J. Ferro (pers. comm., Nov. 8, 2005) has debunked a number of purported "short" proofs of the four-color theorem. Traduction: J. Ferro (communication personnelle du 8 novembre 2005) a démystifié un certain nombre de prétendues courtes preuves du théorème des quatre couleurs. Reference 2: Vertex Coloring of Planar Graphs with Restrictions over Shortest Paths.
2014	/	Toujours pas de preuve classique (sans ordinateur)

Retour	Problème des quatre couleurs Démonstration de Kempe
Suite	Princes de Moebius Quatre couleurs – Index
Voir	Cinq pays Couleurs Démonstration Graphe à 2 couleurs Indicateur d'Euler-Poincaré Introduction à la topologie Quadrichromie Topologie – Glossaire Topologie – Index
DicoNombre	Nombre 4
Sites	Voir références
Cette page	http://villemin.gerard.free.fr/Wwwgvmm/Geometri/TopoQHis.htm