Хроматический многочлен == Введение == == Раскраска в 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 цвета ==
