Участник: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