Изменения

##Если <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>u,v</tex> в каждом из подграфов <tex>G_1,G_2</tex> меньше <tex>2(\Delta-1)</tex>. Тогда, в одном из данных подграфах <tex> \deg u \leqslant \Delta - 2 </tex> или <tex> \deg v \leqslant \Delta - 2 </tex>. То есть, эти подграфы можно правильно раскрасить в не более чем <tex>\Delta</tex> цветов так, чтобы вершины <tex> u,v </tex> были бы разных цветов. А из этого следует, что граф <tex>G</tex> тоже можно правильно раскрасить в не более чем <tex>\Delta</tex> цветов.

###* Если вершины <tex>u,v</tex> смежны с вершиной <tex>p \in G_2</tex>, тогда мы можем правильно раскрасить <tex>G_2</tex>, где степени вершин <tex>u,v</tex> равны <tex>1</tex>, в не более чем <tex> \Delta </tex> цветов так, чтобы вершины <tex>u,v</tex> были одного цвета. Следовательно, можно покрасить граф <tex>G</tex> в не более чем <tex>\Delta</tex> цветов.

###*[[Файл:Brooks_2.png‎|400px|thumb|Алгоритм раскраски. Третий случай, пятый шаг]]Если вершины <tex>u,v</tex> смежны с вершинами <tex>u_1,v_1 \in G_2</tex> соответственно, тогда вместо вершин <tex>\{u,v\}</tex> рассмотрим вершины <tex>\{u,v_1\}</tex>. Заметим, что при удалении этих вершин граф потеряет связность и между ними нет ребра. При этом, сумма степеней новой пары вершин в каждой из компонент, полученных после их удаления, меньше <tex>2(\Delta-1)</tex>. Поэтому, если для этой пары вершин провести рассуждения аналогичные тем, которые проводились для вершин <tex> v,u</tex>, получится, что граф <tex> G</tex> можно правильно раскрасить в не более чем <tex>\Delta </tex> цветов.