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