De combien de couleurs a-t-on besoin au minimum pour colorier n’importe quelle carte géographique, avec la contrainte que deux pays partageant une frontière commune doivent être coloriés de couleur différente? Le théorème des quatre couleurs affirme que quatre couleurs suffisent. Ce théorème a été prouvé en 1976 par Kenneth Appel et Wolfgang Haken : à l’époque c’était le premier théorème prouvé à l’ordinateur. Et maintenant, au 21e siècle, il continue à fasciner les mathématiciens.
Dans tout atlas géographique, on utilise plusieurs couleurs pour colorier les pays. Et on utilise une couleur différente pour les lacs et les océans. Quel est le nombre minimal de couleurs dont on a besoin?
On va oublier la contrainte d’utiliser la même couleur pour les lacs et les océans que l’on va simplement regarder comme des régions à colorier au même titre que les pays. La première portion de carte à gauche nous montre immédiatement qu’il faut au moins quatre couleurs.
La seconde portion de carte est coloriée avec cinq couleurs. On peut bien sûr changer le rouge pour du vert et n’en utiliser que quatre! Et supposons que cette carte représente une île. On pourrait alors colorier l’océan qui l’entoure en violet et n’utiliser que quatre couleurs. Oui, mais est-ce encore possible si ces cinq pays forment une portion d’une carte plus grande avec beaucoup d’autres pays?
Montrer que quatre couleurs suffisent pour colorier une carte est un problème très difficile. Historiquement, on a commencé par montrer que six couleurs suffisent. On a raffiné ensuite la preuve pour montrer que cinq couleurs suffisent. Suivirent, coup sur coup, deux preuves erronées que quatre couleurs suffisent, la première, par Kempe, en 1879, et la seconde, par Tait, en 1880. Même si ces preuves se sont avérées erronées, elles contiennent des idées très profondes qui conduiront à la preuve de Appel et Haken en 1976.
La grande idée de la preuve
Supposons que le théorème des quatre couleurs ne soit pas vrai. Alors il existe une carte dont le coloriage requiert au moins cinq couleurs. Prenons alors une carte minimale dont le coloriage requiert cinq couleurs.
Si on construit une carte avec moins de pays dont le coloriage requiert encore cinq couleurs on obtient une contradiction et on a gagné.
Prenons un exemple. La carte ne peut contenir une région comme celle ci-contre. En effet, si la grande carte a besoin d’une cinquième couleur, par exemple le orange, c’est parce que le reste de la carte utilise aussi le rouge. Sinon on pourrait changer le rouge pour du orange et utiliser quatre couleurs. Dans cette carte si j’enlève le pays rouge central j’obtiens une carte plus petite qui a besoin de cinq couleurs !
On va dire que la région est réductible.
Toute l’essence de la preuve du théorème des quatre couleurs revient à montrer que toute carte dont le coloriage nécessiterait cinq couleurs contient une région réductible. Pour systématiser cette démarche, il faut modéliser la carte.
Modéliser une carte par un graphe
De nombreux problèmes mathématiques peuvent se modéliser par un graphe. Dans le cas du coloriage d’une carte, on la modélise par un graphe planaire. Les sommets sont les oints où au moins trois frontières se rejoignent, les arêtes sont les morceaux de frontière entre les sommets. Comme le graphe est dans un plan, les arêtes séparent les faces. Les illustrations à gauche montrent comment modéliser une carte par un graphe. Colorier la carte revient à colorier les faces.
Dans le problème des quatre couleurs, il suffit de se limiter à des graphes connexes, c’est-à-dire en un seul morceau. En effet, si on a deux morceaux de carte qui ne se touchent pas, on choisit la couleur du fond et on colorie indépendamment les deux morceaux.
On veut montrer que toute carte dont le coloriage nécessiterait cinq couleurs contient une région réductible. Quelles sont ces régions réductibles? On va utiliser le fait que dans le graphe d’une carte :
au moins une face n’a pas plus de cinq arêtes.
Ceci suit de la formule d’Euler pour les graphes planaires connexes (voir encadré).
La formule d’Euler pour les graphes planaires connexes
Étant donné un graphe planaire connexe, soit S son nombre de sommets, A, son nombre d’arêtes et F, son nombre de faces (incluant la face infinie). Alors, on a la formule
\[S – A + F = 2. (^*)\]
On appelle degré d’un sommet le nombre d’arêtes issues de ce sommet. Sous l’hypothèse que chaque sommet a au moins degré 3 (ce qui est le cas dans le graphe d’une carte), une conséquence de la formule d’Euler, est que :
\[3S ≤ 2A.\]
En effet, chaque sommet est attaché à au moins trois arêtes et chaque arête est partagée par deux sommets.
D’où
\[S ≤ \frac{2}{3} A.\]
En remplaçant dans (*), cela donne
\[F-\frac{A}{3}≥2. (^{**})\]
Si toutes les faces étaient limitées par au moins six arêtes on aurait,
\[6F ≤ 2A, \]
puisqu’une arête est partagée par deux faces. D’où
\[F – \frac{A}{3} ≤ 0.\]
Contradiction avec (**). Donc, il existe une face qui a au plus cinq arêtes.
Avant de s’attaquer au coloriage à quatre couleurs, regardons celui à six couleurs, puis celui à cinq couleurs.
Toute carte peut être coloriée avec six couleurs
Appliquons la grande idée. S’il existe une carte qui ne peut être coloriée avec six couleurs, alors il existe une carte minimale qui ne peut être coloriée avec six couleurs. Cette carte contient un pays qui n’a pas plus de cinq frontières et qu’on peut donc facilement colorier avec six couleurs.
Enlevons ce pays comme sur la deuxième figure et on obtient une carte plus petite qui ne peut être coloriée avec six couleurs. Contradiction.
Toute carte peut être coloriée avec cinq couleurs
Appliquons encore la grande idée! Supposons qu’il existe une carte qui ne peut être coloriée avec cinq couleurs. Prenons alors une carte minimale qui ne peut être coloriée avec cinq couleurs. Comme ci-contre, il existe un pays qui a au plus cinq frontières, et concentrons-nous sur le cas où il a exactement cinq frontières.
Sur la figure, on voit que le pays bleu et le pays jaune ne se touchent pas. Unifions-les avec le pays central.
Cette carte a moins de pays que la précédente, qui était une carte minimale ne pouvant être coloriée avec cinq couleurs. Donc, comme cette carte est plus petite, elle peut être coloriée avec cinq couleurs (ce n’est pas nécessairement le même coloriage qu’avant). Mais seulement quatre couleurs ont été utilisées pour colorier les pays adjacents à l’ancien pays central. Il reste donc une couleur qu’on peut attribuer à ce pays.
Pour une deuxième fois, on a identifié une région réductible et on a pu se ramener à un problème de coloriage d’une carte plus petite.
Mais, est-on sûr qu’il y a toujours deux pays qui ne partagent pas une frontière commune?
Oui !
Cela demande d’introduire un nouvel outil : le graphe dual d’un graphe (voir encadré).
Graphe dual d’un graphe planaire
Partons d’un graphe planaire. Son graphe dual est construit ainsi : on associe un sommet à chaque face et on met une arête entre deux sommets si les deux faces du graphe initial partagent une arête.
Appliquons cela au graphe de notre carte :
Si les cinq pays qui entourent le pays violet partageaient deux à deux une frontière, le graphe dual serait un graphe complet à cinq sommets (les cinq pays), c’est-à-dire un graphe dans lequel chaque paire de sommets est reliée par une arête. Mais, il est connu que le graphe complet à cinq sommets est non planaire comme on peut s’en convaincre aisément en regardant la figure : il n’y a plus moyen de tracer une arête entre les sommets 1 et 4 qui ne coupe pas les autres arêtes.
Colorier une carte avec quatre couleurs?
On utilise encore la même idée. On suppose que ce n’est pas possible. On prend une carte minimale qui ne peut pas être coloriée avec quatre couleurs et on cherche une carte plus petite non coloriable avec quatre couleurs. On sait que cette carte a une face qui a moins de cinq arêtes. Il y a trois cas à considérer, selon que la face a trois, quatre ou cinq arêtes.
On a déjà vu ci-dessus que le cas d’une face à trois arêtes est réductible.
Si la face à quatre arêtes, il faut travailler un peu plus.
Regardons la carte suivante :
On voit que le rouge et le vert à droite sont isolés. On peut donc les échanger.
On peut maintenant enlever le pays central en le fusionnant avec les deux pays verts : on a donc une configuration réductible!
Mais que faire, s’il y a une chaîne alternant entre le rouge et le vert et joignant les voisins rouge et vert du pays violet?
On remarque que cette chaîne isole le jaune en haut du bleu en bas. On peut alors échanger le jaune et le bleu en bas dans toute la chaine qui les joint.
De nouveau, on peut fusionner le pays central avec les deux pays jaunes : la configuration est encore réductible.
Et si la face a cinq arêtes?
On vu plus haut l’idée de chaîne. Cette idée très puissante a été introduite par Alfred Kempe, et il l’a utilisée en 1879 pour traiter le cas de la face à cinq arêtes et annoncer la preuve du théorème des quatre couleurs. Malheureusement, sa preuve contenait une erreur…
Le théorème des quatre couleurs
Toutes les idées de la preuve de Kenneth Appel et Wolfgang Haken sont là. Ils supposent qu’il existe une carte qui ne peut être coloriée avec quatre couleurs. Ils prennent alors une telle carte minimale. On a vu ci-dessus des exemples de configurations réductibles. L’essence de la preuve est de montrer que toute carte doit contenir une configuration réductible. Mais, le nombre de configurations réductibles à analyser est très grand, si bien que seul un ordinateur peut venir à bout de les analyser. La preuve de Appel et Haken comprend de montrer que toute carte doit contenir au moins une configuration réductible parmi une liste de 1478 configurations réductibles et, bien sûr, de montrer que ces 1478 configurations sont bien réductibles.
Un regain d’intérêt pour le théorème des quatre couleurs
Les mathématiciens n’ont pas abandonné l’espoir qu’il puisse exister une preuve du théorème des quatre couleurs sans recourir à l’ordinateur. En 1880, Peter Guthrie Tait avait aussi publié une preuve qui s’est révélée erronée. Mais, la première partie de sa preuve établit une équivalence entre le théorème des quatre couleurs et un problème de tricoloriage des arêtes d’un graphe planaire sans pont (voir encadré) dont tous le sommets sont de degré 3. C’est ce problème de coloriage d’arêtes qui fascine plusieurs mathématiciens. En particulier, dans leur conférence plénière au Congrès international des mathématiciens de 2018, Peter Kronheimer et Tomasz Mrowka ont annoncé de nouveaux théorèmes de topologie algébrique qui permettront, espèrent-ils, de donner une preuve du problème équivalent de tricoloriage des arêtes d’un graphe sans recours à l’ordinateur.
L’équivalence de Tait
Première étape : pour montrer que le théorème des quatre couleurs est vrai, il suffit de se limiter à des cartes sans pont dont tous les sommets sont de degré 3 (voir encadré).
Les graphes de l’équivalence de Tait
Un graphe est sans pont si on ne peut le rendre non connexe en coupant une seule arête. Voici un graphe avec pont : si on coupe l’arête en trait plus épais on obtient un graphe non connexe.
Le graphe d’une carte est toujours sans pont.
Aussi, pour montrer le théorème des quatre couleurs il suffit de se limiter à des cartes dont tous les sommets sont de degré 3.
En effet, supposons qu’on ait un sommet de degré supérieur à 3.
Si on ajoute un petit pays au dessus du sommet de degré supérieur à 3, alors les nouveaux sommets sont de degré 3, et si on a un coloriage à quatre couleurs de la nouvelle carte, cela nous donne un coloriage à quatre couleurs de l’ancienne carte.
Supposons qu’on puisse colorier la carte avec quatre couleurs, rouge (R), bleu (B), jaune (J) et vert (V). Montrons que cela permet de donner un tricoloriage des arêtes, c’est-à-dire un coloriage des arêtes avec trois couleurs, orange, violet et noir, de telle sorte que les trois arêtes associées à chaque sommet soient de couleur différente.
Il y a trois manières de diviser les quatre couleurs en deux ensembles de deux couleurs. On peut avoir :
I. R, B et V, J ;
II. R, J et B, V ;
III. R, V et B, J
Si l’arête est entre deux faces du groupe I, on la colorie en orange; si elle est entre deux faces du groupe II, on la colorie en violet ; et si elle est entre deux faces du groupe III on la colorie en noir. Réciproquement, supposons qu’on ait un tricoloriage des arêtes du graphe. Alors, on peut donner à une des faces une couleur arbitraire et, de proche en proche, colorier les autres faces de la seule couleur possible compatible avec la couleur des arêtes. On peut se convaincre que ceci donnera un coloriage à quatre couleurs de la carte initiale.
Ainsi montrer le théorème des quatre couleurs devient équivalent à montrer que, pour tout graphe planaire sans pont dont tous les sommets sont de degré 3, il existe un tricoloriage des arêtes du graphe.
Voyons que cette dernière propriété est vraie si le graphe possède un circuit hamiltonien, c’est-à-dire un chemin fermé formé d’une suite d’arêtes qui passe exactement une fois par chaque sommet : voir le chemin orange et violet sur la figure. Remarquons que ce circuit a alors un nombre pair de sommets. En effet, comme chaque sommet est de degré 3, on a 2A = 3S. Donc, 2 divise S. Le circuit hamiltonien lui-même a exactement S arêtes, soit un nombre pair d’arêtes. Alors, on colorie les arêtes du circuit en alternance avec deux couleurs, et on colorie les arêtes restantes avec la troisième couleur. On peut aussi colorier directement la carte. On utilise en alternance deux couleurs à l’intérieur du circuit hamiltonien et deux couleurs à l’extérieur.
Tait a conjecturé que tout graphe sans pont dont tous les sommets sont de degré 3 a un circuit hamiltonien. Cette dernière conjecture est fausse. Voici un exemple de graphe à 46 sommets de degré 3 qui n’a pas de circuit hamiltonien. Pourtant, on peut colorier ses arêtes avec trois couleurs.
Existe-t-il une preuve qui ne nécessite pas le recours à l’ordinateur?
Un tel débat est lancé dans la communauté mathématique chaque fois qu’elle est confrontée à une preuve par l’ordinateur. Dans le cas du théorème des quatre couleurs, il existe d’autres preuves assistées par ordinateur et la communauté ne doute pas que le théorème est vraiment prouvé. Mais, beaucoup de mathématiciens continuent à croire qu’il doit être possible de donner une preuve « classique » du théorème des quatre couleurs, sans recours à l’ordinateur. Par contre, il faut une idée nouvelle. C’est ce qu’ont proposé Peter Kronheimer et Tomasz Mrowka dans leur conférence au Congrès international des mathématiciens de 2018 : soit d’utiliser leurs nouveaux théorèmes de topologie algébrique pour montrer que le problème équivalent de coloriage des arêtes d’un graphe avec trois couleurs est possible. Nous verrons si leur approche sera fructueuse.
Une autre preuve par ordinateur très célèbre est celle par Thomas Hales de la conjecture de Kepler sur l’empilement des sphères, affirmant que l’empilement le plus dense est celui qu’on observe sur les étals d’oranges.1
- Voir « Quel est l’empilement le plus dense ?», Accromath 13.1, 2018 ↩