3.3 Раскраска плоских графов в соответствии с теоремой о четырех красках

Прежде чем решать задачу о раскраске вершин произвольного графа, рассмотрим раскраску простейших подграфов произвольного конечного, связного плоского графа без петель икратных ребер. Слово «простейший» это не характеристика подграфа и тем более не термин, оно указывает на упрощенную структуру подграфа.

Цепи и циклы.

Простой цепью называют чередующуюся последовательность элементов графа — вершин и ребер, в которой все вершины, а, следовательно, и ребра, различны. Если крайние вершины совпадают, то такую простую цепь называют простым циклом.

Поскольку далее речь пойдет о раскраске вершин плоского графа не более, чем четырьмя красками, обозначим их четырьмя символами α, β, γ, δ, соответственно, и назовем эту проблему задачей о четырёх красках.

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

Цепи и циклы с прилегающими ребрами.

Рассмотрим конечную простую цепь с n вершинами и соединим непересекающимися ребрами некоторые или все несмежные вершины. Назовем эти ребра прилегающими ребрами. Покажем, что число т ребер в такой цепи не более, чем 2п – 3.

Если n = 2, то т = 2 · 2 – 3 = 1. Предположим, что n = k – 1 и т ≤ 2(k – 1) – 3. Покажем, что, добавляя еще одну вершину k (при этом число ребер может увеличиться только на два), число ребер не превзойдет 2k – 3.

т_k= т_k-1 + 2 ≤ 2(k – 1) – 3 + 2 = 2k – 2 – 3 + 2 = 2k – 3.

Поэтому по индукции заключаем, что это неравенство выполняется для любых значений k и, в частности, для k = n т. е.

т ≤ 2k – 3, (*)

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

Можно убедиться в том, что все вершины любой цепи, и любого цикла с прилегающими ребрами раскрашиваются не более, чем тремя цветами. Действительно, пусть дана цепь или цикл с k вершинами — v₁, v₂, ..., v_k.

Раскрасим вершину v₁ в цвет α, вершину v₂ — в цвет β, вершину v₃ — в цвет γ, если (v₁,_v₃) прилегающее ребро.

Следующую вершину v₄ можно раскрасить в цвет α, если вершины v₁ и v₄ несмежны, если же вершины v₁ и v₄ смежны — то в цвет β.

Вершину 5 можно раскрасить в цвет α, если нет прилегающего ребра (v₁,_v₅) или в цвет β, если (v₁,_v₅) прилегающее ребро и т. д.

Таким образом для очередной раскрашиваемой вершины всегда найдется один из трех цветов такой вершины, которая «прикрыта» одним из прилегающих ребер, концы которых несмежны раскрашиваемой вершины. Любые две смежные вершины в плоском графе соединяются любой непрерывной жордановой линией, и потому все ребра в плоском графе пересекаются только в вершинах графа.

Циклы с вершинами внутри.

Рассмотрим произвольный конечный цикл и точку внутри него, соединенную ребрами со всеми вершинами цикла. Такой граф может быть раскрашен не более, чем тремя цветами, если окружающий внутреннюю точку цикл является многоугольником, не обязательно выпуклым, с четным числом вершин, а ребра, соединяющие внутреннюю точку с вершинами, являются какими угодно непрерывными жордановыми линиями. В этом случае одной краской раскрашивается внутренняя вершина, а двумя — вершины многоугольника. Аналогично рассуждая, для раскраски произвольного многоугольника с нечетным числом вершин и внутренней точкой, соединённой ребрами со всеми вершинами, требуется уже четыре краски.