Индукция в графах и теорема Турана

Построим граф на лекциях, как на вершинах. Будем соединять их ребром, если есть общий школьник. Тогда наша задача состоит в том, чтобы покрасить этот граф в цветов. Для этого найдем вершину, у которой степень не более Тогда мы сможем доказать задачу по индукции. Удалить эту вершину и применить предположение, а потом вернуть её и покрасить в свободный от цвета соседей цвет. Теперь будем искать эту вершину. Рассмотрим лекции с минимальным количеством людей равным Докажем, что степень этой вершины как раз не превосходит Возьмем ученика из этой лекции и попытаемся оценить, на сколько лекций он еще сходил. Заметим, что на каждой из этих лекций еще хотя бы ученик, но при этом учеников осталось Тогда количество лекций, на которые сходил этот ученик не больше А значит, степень лекции можно оценить сверху числом Для начала заметим, что при оценку можно улучшить, так как число лекций должно быть целым, а значит, получаем оценку

При хватит нашей оценки. Так как неравенство

равносильно неравенству что верно при