Очевидно, любой карте можно поставить в соответствие граф, вершины которого отвечают странам, а если две страны имеют общую границу, то вершины соединяются ребром. При этом рёбра не пересекаются между собой — такой граф называется плоским. На рис. 2 изображена карта с семью странами (внешняя область — страна), на рис. 3 — соответствующий ей граф с семью вершинами.
Задача о красках эквивалентна следующей задаче о графах: достаточно ли четырёх красок для раскрашивания всех вершин произвольного плоского графа, чтобы любая пара вершин, соединённых ребром, имела разные цвета? Правильная раскраска карты определяет необходимую раскраску графа, и наоборот.
Головоломка. Двое играют в следующую игру. На первом ходу один игрок ставит вершину, другой её раскрашивает. Далее на каждом ходу первый ставит новую вершину, и либо она остаётся изолированной, либо он соединяет её рёбрами с ранее поставленными вершинами; при этом рёбра не должны пересекаться (граф плоский); второй игрок раскрашивает эту вершину и т.д. Какого количества красок достаточно иметь второму игроку, чтобы в возникающем графе любые две вершины, соединённые ребром, были раскрашены в разные цвета?
Решение. После знакомства с задачей о четырёх красках ответ будет весьма неожиданный — не хватит никакого числа красок! Другими словами, первый игрок может действовать таким образом, что второму придётся использовать всё новые и новые краски, и так до бесконечности. Простая и довольно изящная «победная» стратегия показана на рис. 4. (Краски, как обычно, обозначаются цифрами; если требуется новая краска, она получает очередной номер).
Первый игрок ставит вершину, а второй обозначает её цифрой 1 (рис. 4.1) — первая краска. Теперь первый игрок ставит изолированную вершину (она также окрашена в краску 1) и добавляет новую вершину, соединяя её с 1; второй игрок, естественно, ставит 2 (рис. 4.2). Для наглядности рис. 4.2 расположим под рис. 4.1 так, чтобы вершина 2 оказалась под 1.
Ближайшими ходами первый игрок дублирует рис. 4.1 и 4.2 (на рис. 4.3 этот фрагмент обведён пунктиром), затем опять ставит новую вершину и соединяет её с 1 и 2, вынуждая второго поставить на ней 3. Рис. 4.3 расположим под рис. 4.1, 4.2, чтобы вершина 3 оказалась под 1 и 2. Далее первый игрок опять дублирует всю предыдущую игру (рис. 4.4, пунктиром), а новую вершину соединяет с 1, 2 и 3, второй игрок должен поставить на ней 4, рис. 4.4 расположим под рис. 4.1, 4.2, 4.3 и т. д.
Осталось убедиться, что при такой стратегии первого игрока второму не хватит никакого числа красок. Предположим противное: пусть ему достаточно определённого числа k красок. Тогда в какой-то момент получаем рис. 5 пунктиром, причём вершина k расположена под k-1. Теперь первый игрок ставит новую вершину и соединяет её с 1, 2, 3 … k (остальные части графа изображены на рисунке схематически). В результате второй игрок вынужден использовать (k+1)-тую краску. Противоречие!
Но как же быть с гипотезой в задаче о четырёх красках? Всё дело в том, что если в графе, возникающем в процессе игры, стереть все краски, то его легко перекрасить, ограничившись четырьмя красками. Например, граф на рис. 4.3 можно раскрасить в две краски (рис. 6), а не в три. Гипотеза верна для любого графа или географической карты, которые ещё не раскрашены. Но если вершины (страны) раскрашивать в процессе построения графа (карты), как в нашем случае, то, как мы видим, никаких красок не хватит!
