Théorème des 5 couleurs

Dans un graphe planaire, il existe forcément un sommet qui a au plus 5 voisins (exercice).

Tu prends le plus petit graphe (en nombre de sommets) qui ne soit pas "5-coloriable)" et tu colories tous les sommets sauf 1 qui a 5 voisins au plus

Ce sommet est entouré de voisins qui ont tous été coloriés et qui "épuisent" les 5 couleurs.

Ton but: changer la coloration du graphe pour "libérer" une couleur. Dessine sur un broullion un pentagone pour "voir"


Etant donné 2 couleurs a et b comprises entre 1 et 5, tu te demandes si tu peux ou non aller du sommet qui porte a au sommet qui porte b en voyageant à travers le graphe, tes pas consistant à sauter d'un sommet à un voisin mais avec la contrainte que les couleurs franchies soient a-b-a-b-a-b-a... etc

Tu vas arriver à la conclusion facilement toi-même qu'il existe 2 couleurs a,b qui ne sont pas "reliées" dans le sens ci-dessus.

A la manière des dominos chinois, tu changes a en b sur le sommet de départ (un des voisins du sommet non colorié) et tu changes les b en a pour ses voisins, puis les a en b sur les voisins des voisins etc. Ca fera disparaitre a des couleurs voisines du sommet non colorié SANS changer la couleur b de son autre voisin

Tu peux alors colorier le sommet non colorié en a. Contradiction

Qu'entends-tu par "graphe hexagonal"?

Soit tu veux dire 6 sommets reliés 2 à 2, auquel cas il n'est pas planaire

Soit tu veux dire un cycle de longueur 6, auquel cas chaque sommet a 2 voisins

Soit tu veux dire un hexagone avec un septième sommet "au centre" reliés aux sommets de l'hexagine, auquel cas tous les sommets sauf le "centre" ont 3 voisins

Ah oui, on parle de {\bf graphes finis}! Mais la preuve du "théorème des 5 couleurs", elle, passe à l'infini par compacité

Bon je te résume la preuve (qu'il y a un somment avec au + 5 voisins:
C'est dû au fait que par récurrence tu peux prouver que le nombre de sommets + le nombres de "face" - le nb d'arêtes vaut un nombre fixe (3 je crois) (c'est proche de la formule d'Euler, en fait)

Si tu rajoutes un somment avec une arête, tu ne changes pas cette formule
A chaque arête que tu rajoutes (sans toucher aux sommets) tu rajoutes aussi une face.

La formule implique la conclusion qu'il existe un sommet avec moins de 5 voisins: tu "completes" jusqu'à plus pouvoir mettre d'arête (ainsi toutes les faces ont 3 arêtes qui les bordent) ensuite, il suffit d'inspecter les "petits graphes". 6 arêtes par sommets mini, ca impliquerait qu'au total le nb d'arêtes dépasserait 3 fois le nombre de sommets, et 3 fois le nombre de faces donne 2 fois le nombre d'arêtes, ce qui limite les possibilités

Pour info, le fait que 4 couleurs suffisent se démontre de la même manière: j'ai été à une conférence hier où le gars {\bf (Benjamin Werner)} nous a expliqué le principe

La différence (certes énorme sur le plan des calculs) est qu'au lieu de ne s'intéresser qu'aux sommets ayant moins de 5 voisins, on s'intéresse à quelques 700 configurations de ce type (et c'est un ordinateur qui assure qu'elles "marchent")