Проблема четырёх красок в теории графов заключается в том, можно ли раскрасить любую карту, используя только четыре цвета, таким образом, чтобы ни одна из двух соседних областей не имела одинакового цвета. 3

Возникновение гипотезы четырёх красок исторически связано с раскрашиванием географических карт. 1 Если имеется карта с изображением нескольких стран, то граничащие страны необходимо раскрасить в разные цвета. 1 Если каждой стране сопоставить вершину графа и соединить вершины ребром в случае, если страны граничат, то получится планарный граф. 1

В терминах графов теорема о четырёх красках звучит так: для любого планарного графа без петель и кратных рёбер можно раскрасить его вершины в 4 или менее краски так, что у любого ребра концы разноцветные. 5

Теорема о четырёх красках была доказана в 1976 году Кеннетом Аппелем и Вольфгангом Хакеном из Иллинойского университета с помощью компьютера. 4