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

Пусть D(G)=k. Если G не полный граф и не цикл нечетной длины (с нечетным числом вершин), то хроматическое число данного графа не превосходит k.

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

1. Докажем сначала следующее утверждение: Если хроматическое число каждого блока графа не более k, то и хроматическое число всего графа не более k. Воспользуемся индукцией по числу блоков. Для одного блока утверждение очевидно. Пусть для графа из m блоков утверждение верно. Докажем его для m+1 блока. Т.к. b(G) - дерево, то в G есть хотя бы один концевой блок(у дерева есть хотя бы висячая вершина). Покрасим все, кроме этого концевого блока. Т.к. в b(G) он является висячей вершиной, то после покраски всех блоков, кроме этого  в нем будем одна покрашенная вершина. Но тогда этот блок можно покрасить в k цветов. Итак, весь граф из m+1 блоков правильно окрашен в k цветов, т.е. утверждение начала этого пункта верно.
2. В силу леммы 1, достаточно доказать теорему для блока. Блок либо двусвязен (его вершинная связность не меньше 2), либо является K₂, либо K₁. В G не может быть блок K₁, т.к. G связен. Если есть блок K₂, то по условиям теоремы он - не единственный блок графа G. Т.е. (G - связен) есть точка сочленения (в G), принадлежащая G и этому блоку, т.е. есть вершина степени 2, т.е. D(G)2. Но K₂ окрашиваем в 2 цвета, т.е. для него теорема верна. Остается лишь рассмотреть двусвязные графы. Рассмотрим отдельно еще несколько частных случаев блоков. Если блок - K_n, то для него теорема верна (доказывается аналогично со случаем блока K₂). Если блок - простой цикл, то аналогично рассуждениям с K₂, D(G)3. Нечетный цикл правильно окрашиваем в 3 цвета, т.е. для него теорема верна. Остается лишь рассмотреть случай двусвязных неполных графов, у которых D(G)3.
3. Докажем ключевое утверждение данной теоремы. Докажем, что в графах (обозначим их за G), не описанных в пункте 2 есть две вершины a и b, что d(a, b)=2 и граф при удалении этих вершин (G-a-b) не потеряет связность.
   Если в G есть хотя бы одна доминирующая вершина, то выберем в качестве a и b возьмем две несмежные вершины G (они есть, т.к. G - не полный граф). Связность в G-a-b не пропадет, т.к. ни a, ни b не могли быть доминирующими вершинами.
   Разберем теперь случай, когда в G нет доминирующих вершин. Если вершинная связность графа G не менее 3, то при выборе любых двух несмежных вершин в нем в качестве a и b, условия утверждения выполняются.
   Разберем случай, когда вершинная связность G 2. В нем есть вершина степени не меньше 3. Возьмем такую вершину и обозначим ее за z. Если вершинная связность графа G-z (G с удаленной вершиной z) 2, то в качестве a выбираем z, в качестве b - любую вершину на расстоянии 2 от z (такая в G есть, т.к. он - не полный граф).
   Разберем случай, когда вершинная связность графа G-z 1. Тогда в G-z есть хотя бы два блока. Т.к. bc(G-z) - дерево хотя бы с двумя вершинами, то в нем есть хотя бы две висячих вершины, т.е. в G-z есть хотя бы 2 концевых блока. Тогда в них существуют 2 вершины (по одной в каждом концевом блоке), что они в G-z не являются точками сочленения и в графе G были смежны z, иначе бы вершинная связность G была была равна 2. Понятно, что G без этих двух вершин связен (связность в концевых блоках при удалении этих вершин не потерялась, т.е. она не потерялась и в G). Выберем их в этом случае в качестве a и b.
   Разобрав все случаи графа G, получили, что для него утверждение начала части 3 верно.
4. Покажем теперь, как окрасить G в D(G) цветов (G по-прежнему двусвязный неполный граф, у которого D(G)3). Обозначим теперь за z' вершину, смежную с a и b. Пусть |G|=n. G-a-b связен, причем |G-a-b|=n-2. Занумеруем все его вершины по следующему принципу: пусть у вершины z' номер 1. Если еще не занумерованная вершина смежна с уже занумерованной, то занумеруем ее минимальным номером, не встречающемся в нумерации других вершин G-a-b. Таким образом, мы занумеровали все вершины G-a-b номерами от 1 до n-2, что любая вершина, кроме 1-ой (z') смежна с вершиной с меньшим номером (все вершины пронумерованы, т.к. G-a-b связен).
   Приступим теперь непосредственно к окраске G. Окрасим a и b в 1-ый цвет. Теперь красим вершины с номерами n-2, n-3, ..., 2 соответственно по следующему принципу: красим вершину с номером w в цвет, не встречавшийся среди среди ее (w) окрашенных соседей. В силу свойств нумерации, окрашенных соседей у w меньше D(G), т.к. она смежна хотя бы с одной вершиной меньшего номера. Рассмотрим теперь вершину с номером 1 (z'). Если ее степень меньше D(G), то красим ее также, как и вершины с номерами n-2, n-3, ..., 2. Если же ее степень равна D(G), то заметим, что среди ее соседей есть a и b, окрашенные в один цвет, т.е. в окружении вершины z' представлено не более D(G)-1 цветов. Окрасим ее теперь в один из цветов, отличных от цвета любой вершины из ее окружения. Так весь граф G оказался покрашен в D(G) цветов.