Теорема Брукса

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

Лемма:

Пусть [math]G(V,E)[/math] - произвольный связный неориентированный граф и [math]\Delta(G)[/math] - максимальная степень вершин [math]G[/math]. Если в таком графе существует вершина [math]v[/math] степени [math] deg\ v \lt \Delta(G)[/math], то [math]\chi(G) \le \Delta(G)[/math].

Доказательство:

[math]\triangleright[/math]

Запустим алгоритм обхода в ширину из вершины v. Пронумеруем вершины [math]v_1,...,v_n,[/math] где [math]v_i[/math] вершина рассмотренная на [math]i[/math]ом шаге алгоритма bfs. Далее начнем красить вершины в обратном порядке в один из [math]\Delta[/math] цветов так, чтобы никакое ребро графа не соединяло вершины одного цвета. Заметим, что так всегда можно сделать, поскольку на [math] i[/math]ом шаге покраски, для вершины [math] v_{n - i+1}[/math] есть не более [math]\Delta(G) - 1[/math] уже покрашенных соседей, следовательно вершину [math] v_{n-i+1}[/math] можно покрасить по крайней мере в один из свободных цветов. Таким образом граф можно покрасить в [math] \Delta[/math] цветов, следовательно [math] \chi(G) \le \Delta(G)[/math].

[math]\triangleleft[/math]

Теорема (Брукса):

Пусть [math]G(V,E)[/math] — связный неориентированный граф и [math]G[/math] не является [math]K_m[/math] или [math]C_{2m+1}[/math], ни для кого [math] m[/math], то [math]\chi(G) \le \Delta(G)[/math], где [math]\Delta(G)[/math] - максимальная степень вершин [math]G[/math].

Доказательство:

[math]\triangleright[/math]

1)

[math]\triangleleft[/math]