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