286
правок
Изменения
Нет описания правки
}}
Из данного утверждения следует, что в графе существует вершина степени <tex>\leq leqslant 5</tex>.
Вернемся к доказательству нашей теоремы. Будем пытаться доказать от противного. Пусть у нас существует граф, который требует хотя бы 5 цветов для раскраски. Среди всех таких графов существует минимальный, то есть такой, что удаление любой вершины из него делает его 4-раскрашиваемым. Тогда в таком графе не может быть вершины степени <tex> \leq leqslant 3</tex>, так как иначе мы может просто удалить ее из графа, раскрасить полученный граф в 4 цвета, вернуть удаленную вершину и покрасить ее в один из цветов, не занятых соседями. Аналогично [[Хроматическое_число_планарного_графа#Раскраска_в_5_цветов|теореме Хивуда]] доказывается, что удалив вершину степени <tex>4</tex> также всегда можно раскрасить граф в 4 цвета. Следовательно и таких вершин в искомом графе нет. Для вершины степени 5 Кемпе попытался доказать аналогичное утверждение, но это утверждение и было опровергнуто Хивудом. На этом этапе мы и натыкаемся на самую сложную часть доказательства. Имея дело с случаем вершины степени 5, требуются более сложные операции, чем удаление вершины.
На этом этапе мы и натыкаемся на самую сложную часть доказательства. Имея дело с случаем вершины степени 5, требуются более сложные операции, чем удаление вершины. Тогда вместо 1 вершины будем рассматривать связанный подграф из нескольких вершин (назовем его конфигурацией). Тогда для некоторых случаев, как и прежде, достаточно продемонстрировать, что если при удалении конфигурации граф 4-раскрашиваемый, то окраска может быть изменена таким образом, что при возвращении конфигурации граф также можно раскрасить в 4 цвета. Например, конфигурация состоящая из 1 вершины степени <tex>\leqslant 4</tex> является сводимой (было доказано выше). Конфигурации для которых это возможно назовем сводимыми. Неизбежными конфигурациями назовем такие множества конфигураций, что хотя бы одна из конфигураций этого множества обязана быть в нашем графе.
Следовательно, нам осталось найти набор всех неизбежных конфигураций и доказать, что с ними граф все равно 4-раскрашиваем. Основным методом, используемым, чтобы обнаружить такой набор является [https://en.wikipedia.org/wiki/Discharging_method_(discrete_mathematics) метод разрядки]
Приведем пример нахождения неизбежной конфигурации:
{{Утверждение
|statement=В планарном графе есть вершина степени <tex>\leqslant 4</tex> или конфигурация состоящая из 2 вершин степени 5 или из вершины степени 5 и степени 6
|proof=Присвоим каждой вершине <tex>v</tex> некую величину {{---}} '''груз''' <tex>=6-deg(v)</tex>. Предположим что наше утверждение неверно. Следовательно в графе нет вершин степени <tex>\leqslant 4</tex>. Тогда положительный груз есть только у вершин степени 5 (и он равен единице), у вершин степени 6 груз <tex>=0</tex>, а у всех остальных он отрицательный. По доказанному выше утверждению, мы знаем что сумма грузов по всем вершинам <tex>=12 > 0</tex>. Значит вершины степени 5 должны компенсировать все отрицательные грузы других вершин. Пусть каждая такая вершина отдает по <tex>\dfrac{1}{5}</tex> своего груза соседям. Тогда у всех вершин степени 5 и 6 груз останется равен 0 (помним что вершины степени 6 не смежны с вершинами степени 5 по предположению). Рассмотрим все остальные вершины. Так как мы проводим доказательство для триангулированных графов, то у вершины степени <tex>i</tex> не может быть больше чем <tex>\bigg\lfloor\dfrac{i}{2}\bigg\rfloor</tex> соседей степени 5. Однако <tex>(6 - i) + \dfrac{1}{5}\bigg\lfloor\dfrac{i}{2}\bigg\rfloor < 0</tex> для <tex>i \geqslant 7</tex>, следовательно сумма грузов отрицательна. Получено противоречие.
}}
Подобными операциями Аппелем и Хакеном было получено 487 неизбежных конфигураций. Некоторые из них являются сводимыми, а другие требуют механической проверки возможности 4-раскраски. С помощью избавления от сводимых конфигураций и еще ряда эвристик Аппель и Хакен получили 1482 конфигурации, раскрашиванием которых и занимался компьютер.
== Примeчания ==
<references/>
