$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th
Dictionnaire de mathématiques > Dénombrements et probabilités > Théorie des graphes >
Dictionnaire de mathématiques > Histoire > Problèmes célèbres >

Théorème des 4 couleurs

  Prenez une carte du monde, que l'on cherche à colorier en donnant une couleur à chaque pays. Quel nombre minimum de couleurs faut-il pour que deux pays ayant une frontière commune n'aient jamais la même couleur??? On sait que, quels que soient les bouleversements géopolitiques à venir, on pourra se contenter de quatre couleurs.
  Ce résultat peut être énoncé dans le langage de la théorie des graphes. Il s'énonce sous la forme suivante :
Le nombre chromatique d'un graphe planaire est inférieur ou égal à 4.
L'histoire du théorème des quatre couleurs remonte au moins au XIXè siècle. En 1852 Francis Guthrie, mathématicien et botaniste anglais, remarque qu'il lui suffit de quatre couleurs pour colorier la carte des cantons d'Angleterre, sans donner la même couleur à deux cantons qui ont une frontière commune. En 1879, Kempe publie une première "preuve'' de la conjecture, qui est malheureusement fausse. La première démonstration date de 1976, par Appel et Haken. Leur preuve consiste à se ramener à un nombre fini, mais très grand, de configurations. Ensuite, pour chaque configuration, il faut vérifier que 4 couleurs suffisent. Ces nombreuses vérifications ont été faites par ordinateur. Ceci produisit alors une tempête incroyable chez les mathématiciens. C'était la première preuve produite grâce à l'outil informatique. En particulier, on ne pouvait la vérifier humainement! Encore maintenant, on ne connait pas de preuves n'utilisant pas l'ordinateur. En revanche, de nombreuses autres conjectures célèbres ont été démontrées à l'aide de l'informatique, comme la conjecture de Képler.
Consulter aussi...