Теорема о достаточности пяти цветов

Любой планарный граф без петель 5 - раскрашиваем.

Доказательство. При наличии петель граф не может быть правильно раскрашенным, так как концы любого ребра должны быть выкрашены в разные цвета.

При доказательстве теоремы мы воспользуемся леммой, в которой существенным требованием было отсутствие кратных ребер. Для правильной раскраски графа кратные ребра не играют никакой роли. На рис. 31 показано, что кратные ребра мы можем воспринимать как одно ребро.

Если граф несвязный, то задача сводится к правильной раскраске каждой связной компоненты.

Рис. 31

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

Пусть , тогда раскрасим эту вершину одним цветом.

Пусть для графов с утверждение верно.

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

Вернем вершину со всеми инцидентными ребрами. Пусть вершина смежна с вершинами , где .

Возможны три варианта.

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

2. , но среди цветов вершин, с которыми смежна вершина , есть повторяющиеся цвета, тогда вновь остается запасной цвет для вершины .

3. и все вершины, смежные с ней, выкрашены в разные цвета.

Занумеруем вершины, смежные с и обозначим цвет вершины через , как показано на рис. 32. Пусть – связное множество вершин, до которых можно дойти из вершины , идя по вершинам цветов и .

Рис. 32

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

Если вершина , как показано на рис. 33, то перекрашивать вершины в множестве в этом случае бесполезно.

Рис. 33

Тогда рассмотрим множество – связное множество вершин, до которых можно дойти из вершины , идя по вершинам цветов и . Вершина (рис. 33), так как она отделена от вершины циклом. Путь из в не может пересечь ребро – мы рассмотрели геометрическую реализацию графа на плоскости. Этот путь не может пройти и через вершину цикла, поскольку все вершины цикла окрашены в цвета и .

Поменяем в множестве цвета на , на и выкрасим вершину в цвет .

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