2.3. Гипотеза четырех красок.

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

Теорема о пяти красках.

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

«Теорема» о четырех красках (недоказанная).

Каждый пленарный граф можно так раскрасить, используя 4 цвета, что любые две смежные вершины будут окрашены в разные цвета, т. е. , если G — пленарный граф.