Участник:Kirillskor/Задача chromatic-numbers-for-graph-with-degree

Материал из DISCOPAL
Перейти к: навигация, поиск

Добавим условие на связность графа, чтобы убрать тривиальные случаи d = 0, d = 1.

Если d = 2, то G - либо четный цикл, либо дерево, либо нечетный цикл.

Нечетный цикл отпадает по условию, дерево и четный можно раскрасить 2 цветами.

Пусть