Изменения

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