Изменения

Проблема четырех красок на первый взгляд выглядит мало связанной с другими разделами математики и практическими задачами.Однако известно более <tex>20</tex> ее переформулировок, которые связывают эту проблему с задачами алгебры, статистической механики и задачами планирования.  Поэтому начнем Начнем с того, что заменим задачу раскраски плоской карты на эквивалентную ей проблему. Выберем столицу у каждой страны и соединим дугами столицы стран, имеющих общий сегмент границы. В результате получится [[Укладка графа на плоскости|планарный граф]]. Тогда следующая теорема эквивалентна теореме выше:

В таком виде в <tex>1977</tex> году проблема четырех красок была доказана К. Аппелем и У. Хакеном и опубликована в двух статьях <ref>Appel K., Haken W. Every Planar Map Is Four Colorable. Contemporary Mathematics. Providence (R.I.): Amer. Math Soc., 1989. Vol. 98. 308 р.</ref>. Значительную часть проверок выполнил компьютер, из-за чего доказательство было принято не всеми математиками. Дело в том, что даже сами авторы доказательства пишут следующее: Доказательство необычайно велико.

''"Читатель должен разобраться в <tex>50</tex> страницах текста и диаграмм, <tex>85</tex> страницах с почти <tex>2500</tex> дополнительными диаграммами, <tex>400</tex> страницами микрофишей, содержащими еще диаграммы, а также тысячи отдельных проверок утверждений, сделанных в <tex>24</tex> леммах основного текста. Вдобавок читатель узнает, что проверка некоторых фактов потребовала <tex>1200</tex> часов компьютерного времени, а при проверке вручную потребовалось бы гораздо больше. Статьи устрашающи по стилю и длине, и немногие математики прочли их сколько-нибудь подробно"''

|statement=В <tex>G~\nexists </tex> вершины <tex>v \in V</tex> : <tex>dev(v) \leqslant 4</tex>

Если нам удастся найти какую-то неизбежную конфигурацию и доказать, что с ней граф <tex>gG</tex> все равно <tex>4</tex>-раскрашиваем, доказательство будет завершено. Основным методом для нахождения такого набора является [https://en.wikipedia.org/wiki/Discharging_method_(discrete_mathematics) метод разгрузки].

|statement=В планарном графе есть вершина степени не больше <tex>4</tex> или конфигурация , состоящая из <tex>2</tex> вершин степени <tex>5</tex> или из вершины степени <tex>5</tex> и степени <tex>6</tex>|proof=Присвоим каждой вершине <tex>v</tex> некую величину {{---}} '''груз''' <tex>=6-deg(v)</tex>. Предположим что наше утверждение неверно. Следовательно, в графе нет вершин степени не больше<tex>4</tex>. Тогда положительный груз есть только у вершин степени <tex>5</tex> (и он равен единице). У вершин степени <tex>6</tex> груз <tex>=0</tex>, а у всех остальных он отрицательный. По первому доказанному выше утверждению, мы знаем , что сумма грузов по всем вершинам <tex>=12 > 0</tex>. Значит вершины степени <tex>5</tex> должны компенсировать все отрицательные грузы других вершин. Пусть каждая такая вершина отдает по <tex>\dfrac{1}{5}</tex> своего груза соседям. Тогда у всех вершин степени <tex>5</tex> и <tex>6</tex> груз останется равен <tex>0</tex> (помним что вершины степени <tex>6</tex> не смежны с вершинами степени <tex>5</tex> по предположению). Рассмотрим все остальные вершины. Так как мы проводим доказательство для триангулированных графов, то у вершины степени <tex>i</tex> не может быть больше чем <tex>\bigg\lfloor\dfrac{i}{2}\bigg\rfloor</tex> соседей степени <tex>5</tex>. Однако <tex>(6 - i) + \dfrac{1}{5}\bigg\lfloor\dfrac{i}{2}\bigg\rfloor < 0</tex> для <tex>i \geqslant 7</tex>, следовательно, сумма грузов отрицательна. Получено противоречие.