On procède classiquement en nommant les régions puis en traduisant les relations de voisinage à l’aide d’un graphe. Il convient alors de chercher le nombre chromatique du graphe ainsi obtenu.

 

 

 

Nous commençons par nommer les régions.

 

 

 

Nous traduisons maintenant les relations de voisinage à l’aide d’un graphe noté G :

 

 

 

Déterminons maintenant le nombre chromatique du graphe G :

 

Le graphe G comporte plusieurs sous-graphes complets d’ordre 3, chacun d’eux ayant un nombre chromatique égal à 3. On en déduit que le nombre chromatique de G est au moins égal à 3 :

 

 

 

Appliquons maintenant l’algorithme de Welsh-Powell pour obtenir un coloriage de G et majorer .

 

On classe alors les sommets par ordre de degré décroissant :

 

C, E, G (de degré 4), A et D (de degré 3), B et F (de degré 2).

 

L’algorithme fournit alors le coloriage suivant à partir de 4 couleurs :

 

 

On a donc l’encadrement :

 

 

 

Montrons que le graphe peut être colorié avec seulement trois couleurs.

 

Les sommets C et G étant adjacents, ils sont de couleurs différents. On en déduit, les sommets C et G étant tous deux adjacents à E et D, que les sommets E et D sont de la même couleur.

 

En raisonnant de façon analogue avec les sommets C et D, on en déduit que A et G sont de la même couleur.

 

Finalement, on parvient à colorier les deux sommets restants, B et F, de la même couleur que le sommet C. On obtient donc :

 

 

 

Le résultat obtenu nous permet alors de colorier la carte initiale avec trois couleurs :