59
правок
Изменения
→Раскраска в 6 цветов
{{Лемма
|id=5deg_vertex_lemma
|statement=В любом планарном графе <tex> G </tex> существует вершина [[Основные определения теории графов#def_undirected_graph_2 | степени]] не больше <tex>5</tex>.
|proof=
Предположим это не так. Для любой вершины <tex> u_i </tex> графа <tex> G </tex> верно <tex> \mathrm{deg} \; u_i \geqslant 6 </tex>. Если сложить это неравенство для всех <tex> i </tex>, получим <tex> 2E \geqslant 6V </tex>. Но по [[Формула_Эйлера#EulerFormulaCons|следствию из теоремы Эйлера]] <tex> E \leqslant 3V-6 </tex>. Пришли к противоречию.
