Изменения

##Если <tex>G</tex> не является вершинно двусвязным графом, тогда в графе <tex> G</tex> <tex> \exists</tex> <tex> v \in V</tex> {{---}} точка сочленения. Пусть <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>u,v</tex> в каждом из подграфов <tex>G_1,G_2</tex> меньше <tex>2(\Delta-1)</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> цветов.### Если сумма степеней вершин <tex>u,v</tex> в одном из подграфов <tex>G_1,G_2</tex> равна <tex>2(\Delta-1)</tex>.Тогда, степени обоих вершин в одном из подграфов равны <tex> \Delta - 1</tex>, рассмотрим например, что в подграфе <tex>G_1</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> цветов.##Если <tex>G</tex> является <tex>k</tex>-связным графом, где <tex>k > 2</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>. Заметим, что <tex>G_-</tex> связный граф, запустим для <tex>G_-</tex> алгоритм обхода в ширину из вершины <tex>w</tex>. Пронумеруем вершины <tex>v_1,...,v_{n-2}</tex>, где <tex>v_i</tex> вершина рассмотренная на <tex>i</tex>ом шаге алгоритма bfs.Теперь пусть <tex> v_{n-1} = v</tex>,и <tex>v_n = u</tex>. Покрасим <tex>v_n,v_{n-1}</tex> в один цвет, далее начнем красить вершины в обратном порядке, начиная с <tex>v_{n-2}</tex> в один из <tex>\Delta</tex> цветов так, чтобы никакое ребро графа не соединяло вершины одного цвета. Заметим, что так всегда можно сделать, поскольку на <tex> i</tex>ом шаге покраски, где <tex>i \neq n</tex>, для вершины <tex> v_{n - i+1}</tex> есть не более <tex>\Delta(G) - 1</tex> уже покрашенных соседей, следовательно, вершину <tex> v_{n-i+1}</tex> можно покрасить по крайней мере в один из свободных цветов. Вершину <tex>w</tex> мы тоже сможем правильно раскрасить в один из <tex>\Delta</tex> цветов потому, что ее <tex>\Delta</tex> соседей покрашено в не более чем <tex>\Delta - 1</tex> цветов. Таким образом граф <tex> G</tex> можно правильно раскрасить в не более чем <tex>\Delta</tex> цветов.