Изменения
→Вспомогательные Леммы
== Вспомогательные Леммы Вспомогательная Лемма ==
{{Лемма
|statement= Пусть <tex>G(V,E)</tex> - произвольный связный неориентированный граф и <tex>\Delta(G)</tex> - максимальная степень вершин <tex>G</tex>. Если в таком графе существует вершина <tex>v</tex> степени <tex> deg\ v < \Delta(G)</tex>, то <tex>\chi(G) \le \Delta(G)</tex>.
|proof=
Запустим алгоритм [[Обхода в ширину| обхода в ширину]] из вершины v. Пронумеруем вершины <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> v_{n-i+1}</tex> можно покрасить по крайней мере в один из свободных цветов.
Таким образом граф можно покрасить в <tex> \Delta</tex> цветов, следовательно <tex> \chi(G) \le \Delta(G)</tex>.
}}
{{Теорема
|about= Брукса|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>.
|proof=
1)
}}
