== Введение ==
== Раскраска в 6 цветов ==
{{Теорема
|statement=
Пусть граф <tex>G</tex> - планарный. Тогда <tex> \chi (G) \le 6</tex>
|proof=
Докажем по индукции.
* База
Если граф содержит не более 6 вершин, то утверждение очевидно.
* Переход
Предположим, что для планарного графа с <tex>N</tex> вершинами существует раскраска в 6 цветов. Докажем то же для графа с <tex> N+1 </tex> вершиной.
Для начала покажем что найдётся вершина, степень которой не больше 5.
Предположим это не так. Для любой вершины <tex> u_i </tex> верно <tex> deg </tex> <tex> u_i \ge 6 </tex>. Если выписать это неравенство для всех <tex> i </tex> и сложить, получим <tex> 2E \ge 6V </tex>. Но по [[Формула_Эйлера#EulerFormulaCons|следствию из теоремы Эйлера]] <tex> E \le 3V-6 </tex>. Пришли к противоречию.
Теперь, удалим из графа вершину со степенью не превышающей 5. По предположению индукции получившийся граф можно раскрасить в 6 цветов. Вернём удалённую вершину и покрасим её в цвет, не встречающийся среди смежных ей вершин. Индукционный переход доказан
}}
== Раскраска в 5 цветов ==
== Раскраска в 4 цвета ==
