Хроматический многочлен планарного графа

Раскраска в 6 цветов

Теорема:

Пусть граф [math]G[/math] - планарный. Тогда [math] \chi (G) \le 6[/math]

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

[math]\triangleright[/math]

Докажем по индукции. База Если граф содержит не более 6 вершин, то утверждение очевидно. Переход Предположим, что для планарного графа с [math]N[/math] вершинами существует раскраска в 6 цветов. Докажем то же для графа с [math] N+1 [/math] вершиной. Для начала покажем что найдётся вершина, степень которой не больше 5. Предположим это не так. Для любой вершины [math] u_i [/math] верно [math] deg [/math] [math] u_i \ge 6 [/math]. Если выписать это неравенство для всех [math] i [/math] и сложить, получим [math] 2E \ge 6V [/math]. Но по следствию из теоремы Эйлера [math] E \le 3V-6 [/math]. Пришли к противоречию. Теперь, удалим из графа вершину со степенью не превышающей 5. По предположению индукции получившийся граф можно раскрасить в 6 цветов. Вернём удалённую вершину и покрасим её в цвет, не встречающийся среди смежных ей вершин. Индукционный переход доказан

[math]\triangleleft[/math]