QUATRE COULEURS PROBLÈME DES

Carte mentale

Élargissez votre recherche dans Universalis

Triangulations du plan, la formule d'Euler

Ce n'est évidemment pas faciliter la solution que d'ajouter au graphe donné des arêtes de façon qu'il devienne connexe et que toutes ses faces soient des triangles, si ces conditions n'étaient pas réalisées au départ. Il suffit donc de démontrer la proposition pour toutes les triangulations du plan ; si elle est fausse, il existe une triangulation avec un nombre minimal de sommets dont le coloriage exige cinq couleurs. La non-existence de cette triangulation minimale (planaire 5-chromatique) implique le théorème des quatre couleurs.

La démonstration emploie deux outils fondamentaux : la formule d'Euler et les configurations réductibles.

Appelons S, A et F respectivement les nombres de sommets, d'arêtes et de faces d'un graphe planaire (ou sphérique) connexe ; on démontre aisément la formule caractéristique, ou formule d'Euler : S — A + F = 2 (la face extérieure, « infinie », étant comptée). Désignons par pi le nombre de sommets de degré i. On a :

S=ipi, 2 A=iipi,

et, dans le cas d'une triangulation, 2 A = 3 F. On tire de là l'égalité :

i(6i)pi=12,

dont les deux membres sont positifs. On en conclut qu'il existe des sommets de degré ≤ 5 et, comme, dans une triangulation, p0=pi = 0, on arrive à la proposition établie par A. B. Kempe, transcrite ici sous la forme duale :

Une triangulation du plan contient nécessairement un sommet de degré 2, 3, 4 ou 5.

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

Voir aussi

Pour citer l’article

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