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

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

Лемма:

Пусть [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].

Теорема: