Изменения

|statement= Пусть <tex>G(V,E)</tex> {{---}} связный неориентированный граф и <tex>G</tex> не является <tex>K_m</tex> или <tex>C_{2m+1}</tex>, ни для кого <tex> m</tex>, то <tex>\chi(G) \le \Delta(G)</tex>, где <tex>\Delta(G)</tex> - максимальная степень вершин <tex>G</tex>.

#Если <tex> \Delta = 0</tex>, <tex> G = K_1</tex>#Если <tex> \Delta = 1</tex>, <tex> G = K_2</tex>#Если <tex> \Delta = 2</tex>, то:## <tex> G </tex>{{---}} либо дерево либо четный цикл и тогда <tex> \chi(G) = 2</tex>##<tex> G</tex> нечетный циклПоэтому мы будем считать до конца доказательства, что <tex> \Delta(G) \ge 3</tex>.Если в <tex>G</tex> существует вершина <tex>v</tex> степени <tex> deg\ v < \Delta(G)</tex>, то по выше доказанной лемме <tex> \chi(G) \le \Delta(G)</tex>. То есть осталось рассмотреть случай, когда <tex>G</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> G</tex> <tex> \exists</tex> <tex> v,u \in V :(u,v) \notin E</tex> (в противном случаи граф будет полный).