355
правок
Изменения
м
→Теорема
Если в <tex>G</tex> существует вершина <tex>v</tex> степени <tex> deg\ v < \Delta(G)</tex>, то по выше доказанной лемме <tex> \chi(G) \le \Delta(G)</tex>. То есть осталось рассмотреть случай, когда <tex>G</tex> {{---}} регулярный граф степени <tex>\Delta</tex>.
#Если <tex>G</tex> не является вершинно двусвязным графом, тогда в графе <tex> G</tex> <tex> \exists</tex> <tex> v \in V</tex>, где v {{---}} точка сочленения. Пусть <tex>G_1,G_2</tex> две компоненты связности полученный при удалении вершины <tex>v</tex>.Тогда, по выше доказанной лемме <tex>G_1,G_2</tex> можно правильно раскрасить в не более чем <tex>\Delta</tex> цветов.Поскольку количество соседей вершины <tex> v </tex> в каждой из компонент не более <tex> \Delta - 1</tex>, то <tex>G</tex> можно правильно раскрасить в не более чем <tex>\Delta</tex> цветов.
#Если <tex>G</tex> является вершинно двусвязным графом. Тогда, <tex> \exists</tex> <tex> v,u \in V :(u,v) \notin E</tex> и при удалении вершин <tex>v,u</tex> граф теряет связность .Пусть <tex>G_1,G_2</tex> два подграфа <tex> G:(G_1 \cap G_2 = \{v,u\}) \land (G_1 \cup G_2 = G)</tex>. Рассмотрим два случая:
## Если в одном из подграфов <tex> G_1,G_2</tex> <tex> deg\ u \le \Delta - 2 </tex> или <tex> deg\ v \le \Delta - 2 </tex> то, подграфы <tex>G_1,G_2</tex> можно правильно раскрасить в не более чем <tex>\Delta</tex> цветов так, чтобы вершины <tex> u,v </tex> были бы разных цветов.А из этого следует что, граф <tex>G</tex> тоже можно правильно раскрасить в не более чем <tex>\Delta</tex> цветов.
