Pourquoi quatre couleurs suffisent-elles toujours pour colorier une carte ?

Personne n'en connaît de raison courte et satisfaisante. On sait que quatre couleurs suffisent toujours parce qu'un ordinateur l'a vérifié : en 1976, Kenneth Appel et Wolfgang Haken ont prouvé que toute carte peut être coloriée avec au plus quatre couleurs sans que deux régions voisines soient de la même couleur, à condition que « voisines » veuille dire partager une frontière, et pas seulement se toucher en un coin.

L'énigme commence le 23 octobre 1852, quand Francis Guthrie, en coloriant une carte des comtés d'Angleterre, remarque que quatre couleurs lui suffisent. Le démontrer pour toutes les cartes possibles s'est révélé redoutable. Alfred Kempe publie en 1879 une démonstration saluée de toutes parts ; il faudra 11 ans pour que quelqu'un y repère une faille.

La stratégie d'Appel et Haken : montrer qu'une plus petite carte exigeant cinq couleurs ne peut pas exister. Ils ont ramené l'infinité des cartes possibles à 1 834 configurations et fait vérifier chacune par un ordinateur, ce qui a pris plus de mille heures. C'était le premier grand théorème démontré par ordinateur, et certains mathématiciens ont refusé d'accepter une preuve qu'aucun humain ne pouvait vérifier à la main.

Clin d'œil final : les cartographes s'en moquent. Les cartes qui utilisent seulement quatre couleurs sont rares, et la plupart n'en demandent que trois.