Теорема о четырёх красках: любую карту можно раскрасить четырьмя цветами, соседи не совпадают.

Теорема о четырёх красках утверждает, что любую карту — будь то географическая карта государств или схема электрической сети — можно раскрасить всего четырьмя цветами так, чтобы никакие соседние регионы не имели одинаковый цвет. Проблема была впервые сформулирована в 1852 году английским студентом Фрэнсисом Гутри при раскраске карты графств Англии. Попытки найти математическое доказательство заняли 124 года и стали одной из самых известных задач теории графов. Окончательное доказательство теоремы представили в 1976 году Кеннет Аппель и Вольфганг Хакен в Университете Иллинойса. Их подход был революционным: они свели бесконечное множество возможных карт к конечному числу критических случаев — более 1900 конфигураций — и проверили каждую с помощью компьютера IBM. Эта работа стала первым значительным математическим доказательством, которое невозможно было полностью проверить вручную. Программа работала более 1000 часов, что было огромным достижением для вычислительной техники того времени. Теорема имеет прямое применение в практических задачах: при планировании радиочастот для сотовых сетей (чтобы близкие вышки не мешали друг другу), в логистике при проектировании транспортных маршрутов и даже в планировании расписаний без конфликтов. Проблема раскраски графов лежит в основе множества оптимизационных задач в компьютерных науках.