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

@@ Строка 15: / Строка 15: @@
 Пусть теперь все вершины в графе имеют степень d.
+Рассмотрим вершины b, c смежные с a.
+Если удаление b и c делает граф несвязным - то его можно покрасить в d цветов, т.к. в каждой связной компоненте есть вершина степени < d.
+Пусть теперь удаление b, c оставляет граф связным, тогда склеим b и c в вершину d и докажем что G можно раскрасить в d цветов.
+Теперь у a степень d - 1 - значит граф со склееными вершинами можно покрасить в d цветов.
+Теперь в исходном графе покрасим b, c в цвет d.
 <\latex>

Версия 20:17, 9 декабря 2017