Графики и СетиThe Four Colour Theorem

Все эти карты могут быть раскрашены только четырьмя разными цветами, но нетрудно представить, что другим, очень сложным картам может понадобиться гораздо больше цветов. На самом деле, некоторым картам нужно по крайней мере четыре цвета, если они содержат четыре страны, все они связаны друг с другом.

Как и раньше, мы можем преобразовать карту со странами и границами в планарный график: каждая страна становится вершиной край лицо и страны, имеющие общую границу иметь тот же цвет, соединенный ребром:

Теперь мы хотим раскрасить вершины графа, и две вершины должны иметь разный цвет, если они соединены ребром.