Le Théorème des Quatre Couleurs.

Le théorème des quatre couleurs énonce la possibilité de colorier (on dit aussi colorer en théorie des graphes) avec quatre couleurs seulement une carte géographique sans que deux pays voisins aient la même couleur.

Pour être plus précis, en n'utilisant que quatre couleurs différentes, il est possible de colorer n'importe quelle carte découpée en régions connexes (d'un seul morceau), de sorte que deux régions adjacentes (ou limitrophes), c'est-à-dire ayant toute une frontière (et non simplement un point) en commun reçoivent toujours deux couleurs distinctes.
Ainsi, chacune des régions doit recevoir une couleur différente si les régions sont deux à deux adjacentes.

Par ailleurs, il ne peut exister cinq régions connexes deux à deux adjacentes (c'est la partie facile du théorème de Kuratowski).

Application.

Ce théorème a une application pratique dans l'affectation par un opérateur mobile des fréquences GSM aux zones de couverture des stations de base de son réseau. En effet, comme dans la situation des quatre couleurs :

- un réseau GSM est modélisé, comme une carte géographique, par des hexagones contigus : chaque hexagone (appelé "cellule", d'où la notion de réseau cellulaire) correspond au rayonnement d'une station de base (environ 30 kms de diamètre en zone rurale).

- deux hexagones contigus ne doivent en aucun cas se voir attribuer la même bande de fréquences.

Histoire.

La première conjecture des quatre couleurs semble avoir été émise en 1852 par un mathématicien et botaniste Sud Africain, Francis Guthrie (1831 - 1899).

Francis Guthrie était étudiant à l'University College de Londres, où il y suivit les cours du célèbre De Morgan.
Il s'oriente ensuite vers des études de botanique, alors que son frère, Frederick Guthrie, devient mathématicien et suit aussi les cours de De Morgan.
Francis Guthrie remarque qu'il lui suffit de quatre couleurs pour colorer la carte (pourtant complexe) des cantons d'Angleterre, sans donner la même couleur à deux cantons adjacents (ayant une frontière commune).
Il demande alors à son frère Frederick, si cette propriété ne serait pas vraie en général pour toute carte plane ; celui-ci communique la conjecture à De Morgan, et en 1878 Cayley la publie.

• Dès 1879, Kempe trouve une première ''preuve'' de la conjecture, mais onze ans plus tard Heawood y trouvera une faille majeure; il parviendra toutefois à trouver un théorème des cinq couleurs.
  Une seconde ''preuve'' par Tait en 1880 sera de même réfutée par Petersen en 1891.
  
  
• En 1913, le mathématicien américain George David BIRKHOFF (1884 - 1944), démontre la conjecture pour toutes les cartes comportant moins de 26 régions à colorier.
  Cette borne est améliorée au cours du XX^e siècle.
  
  
• En 1969 Heesch trouve des conditions ''presque'' nécessaires et suffisantes pour qu'une configuration soit réductible, et une méthode générale pour trouver un ensemble inévitable de configurations.
  
  

La première preuve effectuée par ordinateur.

• Finalement, en 1976, le mathématiciens américains Kenneth Appel (décédé le 19 avril 2013 à 80 ans) et le mathématicien allemand Wolfgang Haken réalisent le programme de Heesch.
  Ils montrent en utilisant des dizaines de milliers de figures, que toute carte non 4-coloriable doit contenir l'une des 1478 configurations, et, avec 1200 heures de calcul, que ces configurations sont réductibles.
  
  C'est en fait la première preuve informatisée d'un théorème mathématique !

• En 1995, Robertson, Sanders, Seymour et Thomas mettent à profit la formidable accélération des ordinateurs pour trouver une réalisation nettement plus simple du programme de Heesch, avec seulement 633 configurations; de plus ils automatisent également la preuve d'inévitabilité.
  
  
• En Septembre 2012, six ans après la démonstration par ordinateur du théorème des quatre couleurs, Georges Gonthier et son équipe réussissent la démonstration du théorème de Feit et Thompson. Un théorème encore bien plus difficile à formaliser.
  ⇒ En savoir plus [...]