286
правок
Изменения
Нет описания правки
|proof=Так как граф триангулирован, то <tex>2E=3F</tex>, где <tex>E</tex> {{---}} количество ребер, а <tex>F</tex> {{---}} количество граней. Из [[Формула_Эйлера|формулы Эйлера]] <tex>V - E + \dfrac{2}{3}E = 2 ~\rightarrow~ 6V - 2E = 6\sum\limits_{i=1}^{D}v_{i} - \sum\limits_{i=1}^{D}iv_{i} = \sum\limits_{i=1}^{D}(6 - i)v_{i} = 12</tex>
}}
Из данного утверждения следует, что в графе существует вершина степени <tex>\leq 5</tex>.
Вернемся к доказательству нашей теоремы. Будем пытаться доказать от противного. Пусть у нас существует граф, который требует хотя бы 5 цветов для раскраски. Среди всех таких графов существует минимальный, то есть такой, что удаление любой вершины из него делает его 4-раскрашиваемым. Тогда в таком графе не может быть вершины степени <tex> \leq 3</tex>, так как иначе мы может просто удалить ее из графа, раскрасить полученный граф в 4 цвета, вернуть удаленную вершину и покрасить ее в один из цветов, не занятых соседями. Аналогично [[Хроматическое_число_планарного_графа#Раскраска_в_5_цветов|теореме Хивуда]] доказывается, что удалив вершину степени <tex>4</tex> также всегда можно раскрасить граф в 4 цвета. Следовательно и таких вершин в искомом графе нет. Для вершины степени 5 Кемпе попытался доказать аналогичное утверждение, но это утверждение и было опровергнуто Хивудом. На этом этапе мы и натыкаемся на самую сложную часть доказательства. Имея дело с случаем вершины степени 5, требуются более сложные операции, чем удаление вершины.
== Примeчания ==
