308
правок
Изменения
м
Нет описания правки
Для [[Укладка графа на плоскости|планарного графа ]] можно дать оценку сверху на [[Раскраска_графа#chromatic_number_difinition|хроматическое число]].
== Раскраска в 6 цветов ==
|statement=В любом графе <tex> G </tex> существует вершина степени не больше 5
|proof=
Предположим это не так. Для любой вершины <tex> u_i </tex> графа <tex> G </tex> верно <tex> \mathrm{deg } </tex> <tex> u_i \ge 6 </tex>. Если сложить это неравенство для всех <tex> i </tex>, получим <tex> 2E \ge 6V </tex>. Но по [[Формула_Эйлера#EulerFormulaCons|следствию из теоремы Эйлера]] <tex> E \le 3V-6 </tex>. Пришли к противоречию.
}}
== Раскраска в 4 цвета ==
Данная теорема была доказана Кеннетом Аппелем и Вольфгангом Хакеном. Их доказательство сводилось к рассмотрению порядка 2000 графов, 4-раскрашиваемость которых была проверена при помощи компьютера. Подробнее [http://en.wikipedia.org/wiki/Four_color_theorem см. здесь].
== Источники ==
