Изменения

== Вспомогательная Лемма лемма ==

|statement= Пусть <tex>G(V,E)</tex> {{- --}} произвольный [[Отношение связности, компоненты связности|связный ]] неориентированный граф и <tex>\Delta(G)</tex> {{- --}} максимальная степень вершин <tex>G</tex>. Если в таком графе существует вершина <tex>vw</tex> степени <tex> \deg\ v w < \Delta(G)</tex>, то <tex>\chi(G) \le leqslant \Delta(G)</tex>.

[[Файл:Brooks_1.png‎|400px|thumb|Алгоритм раскраски на пятом шаге]]Запустим алгоритм [[Обхода Обход в ширину| обхода в ширину]] из вершины v<tex>w</tex>. Пронумеруем вершины <tex>v_1,...,v_n,</tex> где <tex>v_i</tex> вершина рассмотренная на <tex>i</tex>-ом шаге алгоритма bfs. Далее начнем красить вершины в обратном порядке в один из <tex>\Delta</tex> цветов так, чтобы никакое ребро графа не соединяло вершины одного цвета. Заметим, что так всегда можно сделать, поскольку на На <tex> i</tex>-ом шаге покраски, для вершины <tex> v_{n - i+1}</tex> есть не более <tex>\Delta(G) - 1</tex> уже покрашенных соседей(т.к <tex> \deg(v_{n - i+1}) \leqslant \Delta(G)</tex> и предок данной вершины в дереве bfs еще не покрашен, а если предка нет, то это вершина и есть <tex>w</tex>), следовательно вершину <tex> v_{n-i+1}</tex> можно покрасить по крайней мере в один из свободных цветов.Таким образом Поскольку на каждом шаге алгоритм отработает корректно, следовательно граф можно покрасить правильно раскрасить в не более чем <tex> \Delta</tex> цветов, следовательно то есть <tex> \chi(G) \le leqslant \Delta(G)</tex>.

|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 leqslant \Delta(G)</tex>, где <tex>\Delta(G)</tex> {{- --}} максимальная степень вершин <tex>G</tex>

Для доказательства теоремы рассмотрим несколько случаев:#<tex>\Delta(G) \leqslant 2</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 geqslant 3</tex>., тогда:##Если <tex>G</tex> не является вершинно двусвязным графом, тогда в графе <tex>G</tex> существует вершина <tex> \exists</tex> <tex>v\in V</tex> степени {{---}} [[Отношение связности, компоненты связности|точка сочленения]]. Пусть <tex>G_1,G_2</tex> {{---}} две компоненты связности, полученные при удалении вершины <tex> deg\ v < \Delta(G)</tex>. Тогда, то по выше доказанной лемме эти компоненты можно правильно раскрасить в не более чем <tex> \chi(G) \le Delta</tex> цветов. Поскольку количество соседей вершины <tex> v </tex> в каждой из компонент не более <tex> \Delta(G)- 1</tex>. То есть осталось рассмотреть случай, когда то <tex>G</tex> {{---}} планарный графможно правильно раскрасить в не более чем <tex>\Delta</tex> цветов. ##Если <tex>G</tex> не является вершинно двусвязным графом. Тогда, тогда в графе <tex> G\exists</tex> <tex> v,u \in V :(u,v) \existsnotin E</tex> и при удалении вершин <tex> v \in V,u</tex>граф теряет связность. Пусть <tex>G_1, где v 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>G_1,G_2</tex> равна <tex>2(\Delta-1)</tex>.Тогда, по выше доказанной лемме степени обеих вершин в одном из подграфов равны <tex> \Delta - 1</tex>, рассмотрим например, что в подграфе <tex>G_1</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> цветов.##Если <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> Gi</tex> -ом шаге покраски, где <tex> i \existsneq n</tex>, для вершины <tex> v_{n - i+1}</tex> есть не более <tex>\Delta(G) - 1</tex> vуже покрашенных соседей. Следовательно,u вершину <tex> v_{n-i+1}</tex> можно покрасить по крайней мере в один из свободных цветов. Вершину <tex>w</tex> мы тоже сможем правильно раскрасить в один из <tex>\in V :(uDelta</tex> цветов потому,v) что ее <tex>\notin EDelta</tex> (соседей покрашено в противном случаи не более чем <tex>\Delta - 1</tex> цветов. Таким образом граф будет полный)<tex> G</tex> можно правильно раскрасить в не более чем <tex>\Delta</tex> цветов.    

== Источники См. также ==*[[Раскраска графа]]