Изменения
→Теорема
#Если <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> (в противном случаи и при удалении вершин <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 < \Delta - 2 </tex> или <tex> deg\ v < \Delta - 2 </tex> то, подграфы <tex>G_1,G_2</tex> можно правильно раскрасить в <tex>\Delta</tex> цветов так, чтобы вершины <tex> u,v </tex> были бы разных цветов.А из этого следует что, граф <tex>G</tex> тоже можно правильно раскрасить в <\Delta> цветов.
## Если степени обоих вершин в одном из подграфов равны <tex> \Delta - 1</tex> например в подграфе <tex>G_1</tex>:
##* <tex> G_1,G_2 </tex> можно правильно раскрасить в <tex>\Delta</tex> цветов так, чтобы вершины <tex> u,v </tex> были бы разных цветов.Тогда очевидно, что оценка теоремы выполнена.
##* <tex>\exists p \in G_2: pu \in E \land pv \in E </tex>, тогда мы можем правильно раскрасить <tex>G_2</tex>, где <tex>deg\ u = deg\ v = 1</tex>, в не более чем <tex> \Delta </tex> цветов так, чтобы вершины <tex>u,v</tex> были одного цвета.Следовательно,мы можем можно покрасить граф <tex>G</tex> в не более чем <tex>\Delta</tex> цветов.##*<tex>\exists u_1,v_1 \in G_2: uu_1 \in E \land vv_1 \in E \land u_1 \neq v_1 </tex>, тогда вместо вершин <tex>\{u,v\}</tex> рассмотрим вершины <tex>\{u,v_1\}</tex>.Заметим, что при удалении этих вершин граф потеряет связность и между ними нет ребра,то есть для этой пары вершин можно провести рассуждения аналогичные тем которые проводились для вершин <tex> v,u</tex>, прямым образом вытекает, что граф <tex> G</tex> можно правильно покрасить в не более чем <tex>\Delta </tex> цветов.#Если вышеописанные случаи не подходят, тогда рассмотрим <tex>w \in V : deg\ w = \Delta</tex>. У вершины <tex>w</tex> должны существовать две соседние вершины <tex>u,v : uv \notin E </tex>, в противном случаи <tex>G = K_n</tex>.Пусть <tex>G_- = G - u - v </tex>. Заметим, что H связный граф, запустим на нем алгоритм bfs
}}
