Хроматические графы. Гипотеза четырех красок.

тогда и только тогда, когда граф вполне не связан (не содержит ребер).

Теорема Кенига. тогда и только тогда, когда граф не содержит нечетных простых циклов.

Треугольник и являются примерами 3- и 4- хроматического графа.

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