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