Как хроматическое число связано с проблемой четырех красок?

Хроматическое число связано с проблемой четырёх красок через теорию графов. 13

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

Хроматическое число графа — наименьшее количество красок, с помощью которых можно так раскрасить вершины графа, что любые две вершины, соединённые ребром, окрашиваются при этом в разные цвета. 1

Таким образом, проблема четырёх красок имеет эквивалентную формулировку в теории графов: «Хроматическое число планарного графа не превосходит 4». 35