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