Теорема

Пусть . Тогда

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

1)

Пусть

, - одноцветные классы, . Следовательно,

Но - независимые множества в G. Следовательно, - клики в , а значит

. В свою очередь . Имеем .

2)

Известно, что среднее геометрическое не превосходит среднего арифметического:

3)

Доказательство проведем индукцией по р.

База индукции

Если р=1, то .

Шаг индукции

Пусть для всех графов с (р-1) вершинами. Рассмотрим граф Gс р вершинами, где v– произвольная вершина этого графа. Очевидно, что

и .

Пусть d(v) - степень вершины v. Тогда в графе степень вершины v:

. Имеем . Действительно, и, если бы , то вершину v можно было бы раскрасить в любой из свободных цветов и получить раскраску графа G.

Аналогично, . Таким образом .

4)

Имеем (опять используем то, что среднее арифметическое больше среднего геометрического). Отсюда .