Graphes et réseauxThe Four Colour Theorem

Toutes ces cartes peuvent être colorées avec seulement quatre couleurs différentes, mais il n’est pas difficile d’imaginer que d’autres cartes très complexes pourraient nécessiter beaucoup plus de couleurs. En fait, certaines cartes nécessitent au moins couleurs, lorsqu'elles contiennent quatre pays connectés entre eux.

Comme auparavant, nous pouvons convertir une carte avec des pays et des frontières en un graphique planaire: chaque pays devient un sommetan edgea face et les pays qui partagent une frontièrehave the same colour sont reliés par un bord:

Nous souhaitons maintenant colorer les sommets d'un graphique. Deux sommets doivent avoir une couleur différente s'ils sont connectés par une arête.