3.2 Теорема о четырех красках

Проблема четырёх красок — математическая задача, предложенная Ф. Гутри в 1852 году, сформулированная следующим образом: «Выяснить, можно ли всякую расположенную на сфере карту раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета».

К. Аппель и В. Хакен доказали в 1976 г., что так можно раскрасить любую карту. Это была первая крупная математическая теорема, для доказательства которой был применён компьютер. Несмотря на последующие упрощения, доказательство практически невозможно проверить, не используя компьютер. Поэтому некоторые математики отнеслись к этому доказательству с недоверием, что объяснялось не только использованием компьютера, но и громоздкостью описания алгоритма первых доказательств (741 страница); впоследствии были предложены более компактные алгоритмы и скорректирован ряд ошибок. Проблема четырёх красок является одним из известнейших прецедентов неклассического доказательства в современной математике.

Отметим самую известную интерпретацию проблемы о четырех красках. Пусть имеется географическая карта. Можно ли, используя только 4 краски, изобразить эту карту так, чтобы соседние страны (имеющие общую границу) были окрашены в разный цвет? Понятно, что в соответствующем графе вершинами являются страны, а смежными вершинами являются соседние страны. Ясно, что полученный граф является планарным, и после 1976 г. ответ на этот вопрос является положительным.

Новое доказательство, основанное на алгебраических и топологических методах, дал индийский математик Ашей Дарвадкер в 2000 году.