Теорема. Любой планарный граф можно раскрасить не более, чем пятью красками.

Любой планарный граф можно раскрасить не более, чем пятью красками.

Доказательство

Доказательство будем проводить методом математической индукции по числу вершин.

База индукции.

Очевидно, что утверждение теоремы справедливо, когда плоский граф имеет число вершин, не превышающее 5 (р< =5).

Шаг индукции

Предположим, что наше утверждение справедливо для всех графов с числом вершин р. Рассмотрим граф G с число вершин (р+1). То есть в граф с р вершинами, который мы по предположению можем раскрасить пятью цветами, добавляем еще одну вершину. И задача сводится к раскраске этой новой добавленной вершине.

Согласно следствию из теоремы Эйлера в нашем графе существует хотя бы одна вершина, имеющая степень не более, чем 5. пусть это будет вершина . Если мы удалим эту вершину из нашего графа, то получим граф с р вершинами, для которого справедливо наше предположение. То есть задача раскраски графа G с (р+1) вершинами сводится к раскраске вершины .

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

2) Если . Рассмотрим два случая.

2.1) Среди пяти вершин, смежных с , есть хотя бы две несмежные. Тогда эти вершины раскрашены не более, чем четырьмя цветами. Следовательно, остается один цвет для раскраски .

2.2) Все вершины, смежные с , смежны между собой. Удалим из нашего графа вершину и стянем вершины и в вершину .

Полученный граф G” будет иметь число вершин (р-1) и будет плоским. Следовательно, для него будет выполняться наше предположение. Возьмем любую раскраску графа G” пятью цветами. Используем эту раскраску для всех вершин графа G, совпадающих с G”. Затем раскрасим вершины и в цвет . Тогда вершины, смежные с будут окрашены не более, чем четырьмя красками и один цвет пятый останется для раскраски .