Условие задачи
Граф имеет множество вершин {1,2,3,4,5,6}. Ребра 12, 14, 23, 24, 34, 36, 45, 56.
Найдите хроматическое число и оптимальную раскраску вершин графа.
Ответ
Поскольку в графе есть нечетный цикл, его нельзя раскрасить в два цвета. Значит хроматическое число .