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

Индукция по База при тривиальна.

Переход: если в графе есть вершина степени не больше то выкинем её и разобьём оставшийся граф по предположению на множеств. Если все рёбра, исходящие из выкинутой вершины, взять в отдельные множества, то получим не более множеств. Однако если чётное, то множеств очевидно не больше Если же нечётное, то степень выкинутой вершины не больше тогда множеств максимум

Пусть теперь степень каждой вершины строго больше Выберем вершину наименьшей степени, пусть её степень равна — натуральное. Выделим паросочетание на хотя бы рёбрах, соединяющих вершины, смежные с

Рассмотрим произвольную вершину смежную с Её степень хотя бы Всего не более вершин, не смежных с Значит, соединена хотя бы с вершинами, смежными с Последнее выражение при нечётном равно при чётном — В силу произвольности выбора так можно сказать про любую вершину, смежную с

Рассмотрим вершину смежную с По вышеописанным рассуждениям она соединена с хотя бы вершиной, смежной с Назовём одну из этих вершин — Далее рассмотрим вершину Она, быть может, соединена с и но она еще должна соединяться с хотя бы вершиной, смежной с Одну из них назовём Продолжая эти рассуждения, доходим до и понимаем, что она, возможно, соединена с вершинами однако она ещё должна соединяться с хотя бы одной вершиной, смежной с назовём её Тогда можно рассмотреть рёбра Они образуют паросочетание из рёбер.

Рассмотрим такое разбиение рёбер графа на множества: выделим треугольников Осталось рёбер, выходящих из оставшихся без множества. Каждое из них поместим в отдельное множество. Теперь выкинем вершину и все рёбра, которые уже находятся в множествах. Получился граф на -й вершине, рёбра которого по предположению разбиваются на не более чем нужных нам множеств. Таким образом, всего не более Далее, рассматривая разные случаи чётности нетрудно убедиться, что последняя величина не превосходит