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

Докажем задачу индукцией по

Прежде чем доказывать базу, давайте поймём, какое минимальное значение может быть. Ясно, что оно ограничено, потому что, например, при описанная в задаче конструкция вообще невозможна.

Итак, в графе не более рёбер. Значит откуда . При описанная в условии конструкция реализуется, притом только если граф полный (это следует из рассмотренного неравенства).

База для очевидна, потому что степень каждой вершины то есть можно выкинуть одну вершину и степень остальных будет по

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

Если же её степень хотя бы то и степень всех остальных хотя бы Значит, если её выкинуть, то степень соседних с ней вершин будет хотя бы а у несоседних — хотя бы Что и требовалось.