Изменения

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

Запустим алгоритм [[Обход в ширину|обхода в ширину]] из вершины <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 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) \le leqslant 2</tex>, тогда:

#*# <tex> G </tex>{{---}} либо дерево либо четный цикл и тогда <tex> \chi(G) = 2</tex>

#<tex>\Delta(G) \ge geqslant 3</tex>, тогда:

### Если сумма степеней вершин <tex>u,v</tex> в каждом из подграфов <tex>G_1,G_2</tex> меньше <tex>2(\Delta-1)</tex>. Тогда, в одном из данных подграфах <tex> \deg\ u \le leqslant \Delta - 2 </tex> или <tex> \deg\ v \le leqslant \Delta - 2 </tex>. То есть, эти подграфы можно правильно раскрасить в не более чем <tex>\Delta</tex> цветов так, чтобы вершины <tex> u,v </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> цветов.

== Источники информации ==