Изменения

== Общие идеи доказательства ==Проблема четырех красок на первый взгляд выглядит мало связанной с другими разделами математики и практическими задачами.Однако известно более <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>. Значительную часть проверок выполнил компьютер, как из-за чего доказательство было сказано выше, вызывает до сих пор определенный скептицизмпринято не всеми математиками. Дело в том, что даже сами авторы доказательства пишут следующее:

Говоря прямоОчевидно, компьютерную часть что из-за сложности доказательства почти невозможно проверить вручную, а традиционная часть доказательства длинна и сложна настолько, что ее никто мы не сможем рассмотреть его целиком и не проверял. Некоторое время назад появилось новое доказательство <ref>Thomas R. An Update on the Four-Color Theorem // Not. Amer. Math. Soc. 1998. Vol. 45, № 7. Р. 848–859.</ref>, причем та часть, которая выполнена не но посмотрим на компьютереобщие идеи, уже поддается проверке. Однако компьютерная часть все еще остается скорее предметом верыкоторые в нем используются.

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

Из данного утверждения следует, что в графе существует вершина степени не больше <tex>5</tex>. Попытаемся доказать теорему от противного. Пусть у нас существует граф, который требует хотя бы <tex>5</tex> цветов для раскраски. Среди всех таких графов существует минимальный, то есть такой граф <tex>G</tex>, что удаление любой вершины из него делает его <tex>4</tex>-раскрашиваемым.  {{Утверждение|statement=В <tex>G~\nexists </tex> вершины <tex>v \in V</tex> : <tex>dev(v) \leqslant 54</tex>|proof=Если в <tex>G</tex> есть вершина степени <tex>3</tex>, то мы можем просто удалить ее из графа, раскрасить полученный граф в <tex>4</tex> цвета, вернуть удаленную вершину и покрасить ее в один из цветов, не занятых соседями. Аналогично [[Хроматическое_число_планарного_графа#Раскраска_в_5_цветов|теореме Хивуда]] доказывается, что удалив вершину степени <tex>4</tex> также всегда можно раскрасить граф в <tex>4</tex>цвета.}}

Вернемся к доказательству нашей теоремы. Будем пытаться доказать от противного. Пусть у нас существует граф, который требует хотя бы <tex>5</tex> цветов для раскраски. Среди всех таких графов существует минимальный, то есть такой, что удаление любой вершины из него делает его <tex>4</tex>-раскрашиваемым. Тогда в таком графе не может быть вершины степени <tex> \leqslant 3</tex>, так как иначе мы может просто удалить ее из графа, раскрасить полученный граф в <tex>4</tex> цвета, вернуть удаленную вершину и покрасить ее в один из цветов, не занятых соседями. Аналогично [[Хроматическое_число_планарного_графа#Раскраска_в_5_цветов|теореме Хивуда]] доказывается, что удалив вершину степени <tex>4</tex> также всегда можно раскрасить граф в <tex>4</tex> цвета. Следовательно, и таких вершин в искомом графе нет. Для вершины степени <tex>5</tex> Кемпе попытался доказать аналогичное утверждениеневерно, но это утверждение хотя оно и было опровергнуто Хивудомприсутствовало в одном из первых ошибочных доказательств.

На этом этапе мы и натыкаемся на самую сложную часть доказательства. Имея дело со случаем вершины степени <tex>5</tex>, требуются более сложные операции, чем удаление вершинынельзя просто удалить ее. Тогда вместо <tex>1</tex> вершины будем рассматривать связанный подграф из нескольких вершин (назовем его '''конфигурацией'''). Тогда для некоторых случаев, как и прежде, достаточно продемонстрировать, что если при удалении конфигурации граф <tex>4</tex>-раскрашиваемый, то окраска может быть изменена таким образом, что при возвращении конфигурации граф также можно раскрасить в <tex>4</tex> цвета. Конфигурации для которых это возможно назовем '''сводимыми'''. Например, конфигурация состоящая из <tex>1</tex> вершины степени <tex>\leqslant 4</tex> является сводимой (было доказано выше). '''Неизбежной''' конфигурацией назовем такое '''множество''' конфигураций, что хотя бы одна из конфигураций этого множества обязана быть в нашем графе.