Pourquoi deux pays voisins n'ont jamais la même couleur

Regardez la carte de l'Europe une minute. La France est jaune, l'Espagne rose, l'Allemagne verte, la Belgique bleue. Aucun pays ne touche un pays de sa couleur. Ce n'est pas de la chance, et ce n'est pas un choix esthétique : c'est calculé avant que vous n'arriviez sur la page.

Une question posée en 1852

Un étudiant britannique, Francis Guthrie, colorie une carte des comtés d'Angleterre. Il remarque qu'il y arrive toujours avec quatre couleurs, jamais besoin d'une cinquième. Il en parle à son frère, qui en parle à son professeur, et la question part en circulation : quatre couleurs suffisent-elles pour n'importe quelle carte ?

La question est facile à poser et terriblement difficile à trancher. Elle résiste cent vingt-quatre ans.

Une fausse démonstration publiée en 1879 tient onze ans avant qu'on y trouve le trou. Une autre suit, fausse aussi. Pendant tout ce temps, personne ne trouve de carte exigeant cinq couleurs, et personne n'arrive à prouver qu'elle n'existe pas.

La preuve tombe en 1976, à l'université de l'Illinois. Kenneth Appel et Wolfgang Haken ramènent le problème à un catalogue fini de configurations, puis font vérifier chacune par ordinateur, pendant plus de mille heures de calcul. C'est la première grande démonstration mathématique qu'aucun humain ne peut relire entièrement à la main, et elle déclenche une querelle qui dure encore : une preuve que personne ne peut vérifier de bout en bout est-elle une preuve ?

Le résultat, lui, tient. Quatre couleurs suffisent.

Ce que le théorème dit exactement

Il ne parle pas de pays, il parle de régions du plan qui se touchent par une frontière, pas par un simple point. Deux régions qui ne se rejoignent qu'en un coin, comme les États de l'Utah et du Nouveau-Mexique, peuvent partager leur couleur sans gêner personne.

Il suppose aussi que chaque pays est d'un seul tenant. Un pays en morceaux séparés qu'il faudrait colorier à l'identique casse la démonstration, et il en existe : l'enclave espagnole de Melilla, les exclaves russes, l'Alaska détaché du reste des États-Unis. Dans la pratique cartographique, on les colorie souvent chacun de son côté, et le problème disparaît.

Comment ce site s'en sert

Les cartes d'ici ne sont pas des images. Ce sont des tracés calculés à partir de Natural Earth, un jeu de données cartographiques du domaine public, et la couleur est attribuée à la compilation, une fois pour toutes.

Le calcul se fait en trois temps.

D'abord, qui touche qui. Les frontières ne sont pas stockées pays par pays mais sous forme d'arcs partagés : la frontière franco-belge est un seul tracé, que la France et la Belgique se partagent. Deux pays qui se partagent un arc sont voisins, et cela se lit directement, sans comparer des millions de points de coordonnées.

Ensuite, l'ordre de coloriage. On ne colorie pas les pays dans l'ordre alphabétique, ce serait le meilleur moyen de se coincer. On commence par le pays le plus contraint, celui dont les voisins ont déjà pris le plus de couleurs différentes, et on continue ainsi. Cette méthode porte un nom, DSATUR, et elle produit de bons coloriages en une seule passe.

Enfin, le choix de la teinte. Le site dispose de huit couleurs, rangées en quatre familles de deux : les bleus, les soleils, les verts, les roses. La règle est plus stricte que le théorème : deux voisins ne doivent pas seulement éviter la même couleur, ils doivent éviter la même famille. Quatre familles, exactement le minimum que garantit le théorème. Les deux nuances à l'intérieur d'une famille n'apportent que de la variété, jamais du contraste : elles ne se retrouvent jamais côte à côte.

Pourquoi se donner ce mal

Parce qu'un jeu de cartes où l'on cherche un pays est d'abord un exercice de lecture visuelle. Si deux voisins se ressemblent, le regard hésite, et l'hésitation n'a rien à voir avec la géographie : elle vient du graphisme. Autant la supprimer.

Il y a une deuxième raison, moins évidente. Environ un homme sur douze et une femme sur deux cents perçoivent mal les rouges et les verts. Une carte qui ne joue que sur la teinte leur devient illisible par endroits. C'est pourquoi la couleur n'est jamais seule à séparer deux pays ici : un trait sombre d'un peu plus d'un pixel cerne chaque frontière, et c'est lui, au fond, le vrai garant de la lisibilité. La couleur rend la carte agréable ; le trait la rend utilisable.

C'est aussi pour cela que le juste et le faux ne sont jamais signalés par du vert contre du rouge. Une bonne réponse se remplit et s'épaissit. Une erreur se hachure. La forme parle avant la couleur.

Essayez de le prendre en défaut

Ouvrez n'importe quelle carte du site et cherchez deux pays voisins de la même famille de couleurs. Vous n'en trouverez pas, et maintenant vous savez pourquoi : ce n'est pas que personne n'a essayé de vous piéger, c'est qu'un théorème de 1976 garantit que le cas n'arrivera jamais.