Участник:Kirillskor/Задача chromatic-numbers-for-graph-with-degree — различия между версиями
Материал из DISCOPAL
Строка 15: | Строка 15: | ||
Пусть теперь все вершины в графе имеют степень d. | Пусть теперь все вершины в графе имеют степень d. | ||
+ | |||
+ | Рассмотрим вершины b, c смежные с a. | ||
+ | |||
+ | Если удаление b и c делает граф несвязным - то его можно покрасить в d цветов, т.к. в каждой связной компоненте есть вершина степени < d. | ||
+ | |||
+ | Пусть теперь удаление b, c оставляет граф связным, тогда склеим b и c в вершину d и докажем что G можно раскрасить в d цветов. | ||
+ | |||
+ | Теперь у a степень d - 1 - значит граф со склееными вершинами можно покрасить в d цветов. | ||
+ | |||
+ | Теперь в исходном графе покрасим b, c в цвет d. | ||
<\latex> | <\latex> |
Версия 20:17, 9 декабря 2017