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