Участник:Kirillskor/Задача chromatic-numbers-for-graph-with-degree — различия между версиями
Материал из DISCOPAL
Строка 7: | Строка 7: | ||
Пусть d \geq 3: | Пусть d \geq 3: | ||
+ | |||
+ | |||
Докажем, что если в графе есть вершина u, со степенью < d, его можно покрасить в d цветов. | Докажем, что если в графе есть вершина u, со степенью < d, его можно покрасить в d цветов. | ||
Строка 13: | Строка 15: | ||
Начнем красить с последней вершины: на каждом шаге у текущей вершины v есть не более d-1 покрашенных соседей, т.к. ее степень \leq d, а ее предок не покрашен, либо это вершина u и у нее по определению < d соседей. | Начнем красить с последней вершины: на каждом шаге у текущей вершины v есть не более d-1 покрашенных соседей, т.к. ее степень \leq d, а ее предок не покрашен, либо это вершина u и у нее по определению < d соседей. | ||
+ | |||
+ | |||
Пусть теперь все вершины в графе имеют степень d. | Пусть теперь все вершины в графе имеют степень d. |
Версия 20:17, 9 декабря 2017