Участник:Kirillskor/Задача chromatic-numbers-for-graph-with-degree — различия между версиями

Пусть d \geq 3:

Пусть d \geq 3:

Докажем, что если в графе есть вершина u, со степенью < d, его можно покрасить в d цветов.

Докажем, что если в графе есть вершина u, со степенью < d, его можно покрасить в d цветов.

Начнем красить с последней вершины: на каждом шаге у текущей вершины v есть не более d-1 покрашенных соседей, т.к. ее степень \leq d, а ее предок не покрашен, либо это вершина u и у нее по определению < d соседей.

Начнем красить с последней вершины: на каждом шаге у текущей вершины v есть не более d-1 покрашенных соседей, т.к. ее степень \leq d, а ее предок не покрашен, либо это вершина u и у нее по определению < d соседей.

Пусть теперь все вершины в графе имеют степень d.

Пусть теперь все вершины в графе имеют степень d.