Ух, . . . ,Vn одноцветные классы,доказательство

1=1

1. Пусть x(G) =

следовательно,

j ^ р/п.

г=1

Но VJ — независимые множества в G, следовательно, Vi — клики в G. Значит,

X ^ maxpi ^ р/п.

г=1

Имеем

> п • р/п = р.

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

а + Ь

аи.

Следовательно, х + X

3. Докажем индукцией по р, что х + X ^ Р + 1- База: р = 1 =?> х = 1 & X = 1. Пусть х + X ^ Р Д^{ля всех} графов с р - 1 вершинами. Рассмотрим граф G с р вершинами и вершину v £ V. Тогда, очевидно,

_X(G) < _X(G - v) + 1 & x(G) < x(G - и) + 1. Если x(G) < x(G - v) + 1 V x(G) < x(G~ - v) + 1, то

X + X = X(G) + x(G) <_X(G-v) + l + x(G-v) + l^p+2. Следовательно, х + Х^Р + 1- Пусть теперь

_X(G) - _X(G ~ v) + 1 & X(G) = x(G - u) + 1.

Положим d : = d(w) в графе G, тогда d = p-d-l — степень v в графе G. Имеем d ^ x(G - v). Действительно, x(G) = x(G - г)) + 1 и, если бы d < x(G - г>), то вершину v можно было бы раскрасить в любой из свободных x(G - v) - d цветов и получить x(G - v) -раскраску графа G.

Аналогично, d = р - d- l^ x(G - v). Таким образом,