QUATRE COULEURS PROBLÈME DES

Carte mentale

Élargissez votre recherche dans Universalis

Les configurations réductibles

Appelons configuration dans une triangulation T un sous-graphe constitué d'un circuit C et des sommets et arêtes situés à l'intérieur de C dans le plan, cette partie intérieure comprenant au moins un sommet. C est appelé le circuit séparateur de la configuration. Dans une triangulation, tout sommet avec ses voisins forme une configuration. Un triangle de sommets de degré 5 qu'entoure un circuit C6 est un autre exemple.

La proposition de Kempe, donnée plus haut, met en évidence le premier ensemble inévitable de configurations dans un graphe planaire triangulé.

Supposons que l'on puisse déduire de T une triangulation T' telle que :

– l'intérieur de C soit modifié de façon à diminuer le nombre des sommets ;

– C lui-même ne soit modifié que par l'identification de certains sommets (non consécutifs sur C) ;

– la partie extérieure à C soit isomorphe dans T et T', aux identifications de sommets de C près ;

– T' ne comporte pas de boucles.

Si la colorabilité de T' (avec quatre couleurs) implique celle de T, alors T ne sera pas une triangulation minimale, car la nécessité de cinq couleurs pour colorier T entraîne cette même nécessité pour T', qui a moins de sommets. Le sous-graphe constitué de C et de son intérieur sera défini comme une configuration réductible, et sa présence dans une triangulation suffit à démontrer que celle-ci n'est pas minimale. Si l'on parvient à montrer que toute triangulation contient une configuration réductible, on aura démontré, d'après tout ce qui précède, qu'aucun graphe planaire n'exige cinq couleurs pour le coloriage de ses sommets.

En résumé, la preuve du théorème des quatre couleurs consiste à produire un ensemble inévitable de configurations réductibles.

1  2  3  4  5
pour nos abonnés,
l’article se compose de 4 pages

Médias de l’article

Réduction d'une configuration v4 d'un graphe planaire triangulé

Réduction d'une configuration v4 d'un graphe planaire triangulé
Crédits : Encyclopædia Universalis France

dessin

Réductibilité d'un quadrilatère

Réductibilité d'un quadrilatère
Crédits : Encyclopædia Universalis France

dessin

Afficher les 2 médias de l'article


Écrit par :

  • : docteur ès lettres, professeur à l'université Paul-Valéry de Montpellier

Classification

Autres références

«  QUATRE COULEURS PROBLÈME DES  » est également traité dans :

APPEL KENNETH (1932-2013)

  • Écrit par 
  • Melinda C. SHEPHERD
  •  • 380 mots

Le mathématicien américain Kenneth Appel apporta, avec son confrère Wolfgang Haken, la preuve du problème dit des quatre couleurs en 1976. Kenneth Ira Appel naît le 8 octobre 1932, dans le quartier new-yorkais de Brooklyn. Il étudie les mathématiques au Queens College de New York, où il décroche une licence en 1953, puis à l’université du Michigan, où il passe un doctorat en 1959. Dès l’obtenti […] Lire la suite

INFORMATIQUE ET VÉRITÉ MATHÉMATIQUE

  • Écrit par 
  • Jean-Paul DELAHAYE
  •  • 1 990 mots
  •  • 1 média

Dans le chapitre « Preuves mathématiques classiques avec ordinateur »  : […] Si l'ordinateur peut conduire à de quasi-certitudes en dehors de la méthode hilbertienne, il peut aussi produire des preuves mathématiques classiques. Plusieurs cas sont possibles, que nous allons présenter en insistant sur ce qui les distingue. Certaines techniques de démonstration automatique produisent des démonstrations qu'aucun humain n'avait découvertes sans aide informatique, mais qui, une […] Lire la suite

Pour citer l’article

Jean MAYER, « QUATRE COULEURS PROBLÈME DES », Encyclopædia Universalis [en ligne], consulté le 18 mai 2022. URL : https://www.universalis.fr/encyclopedie/probleme-des-quatre-couleurs/