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