QUATRE COULEURS PROBLÈME DES

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 p_i le nombre de sommets de degré i. On a :

$$\mathrm{S}=\sum _i{p}_i, 2 \mathrm{A}=\sum _i{ip}_i,$$

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

$$\sum _i(6–i)p_i=12,$$

dont les deux membres sont positifs. On en conclut qu'il existe des sommets de degré ≤ 5 et, comme, dans une triangulation, p₀=p_i = 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.