Участник:Kirillskor/Задача chromatic-numbers-for-graph-with-degree — различия между версиями
Материал из DISCOPAL
| Строка 5: | Строка 5: | ||
Нечетный цикл отпадает по условию, дерево и четный можно раскрасить 2 цветами. | Нечетный цикл отпадает по условию, дерево и четный можно раскрасить 2 цветами. | ||
| − | Пусть <latex>d \geq 3 <\latex>: | + | Пусть <latex> d \geq 3 <\latex>: |
Версия 20:18, 9 декабря 2017
Добавим условие на связность графа, чтобы убрать тривиальные случаи d = 0, d = 1.
Если d = 2, то G - либо четный цикл, либо дерево, либо нечетный цикл.
Нечетный цикл отпадает по условию, дерево и четный можно раскрасить 2 цветами.
Пусть