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

Первое решение. Докажем сначала следующую лемму.

Лемма. Если в графе на вершинах нет треугольников, то в нём не более рёбер.

Доказательство. Рассмотрим вершину наибольшей степени (пусть Пусть вершина cоединена с Ясно, что никакие и не могут быть соединены, потому что иначе в графе будет треугольник Степень оставшихся вершин не превосходит Таким образом, всего в графе не более Лемма доказана.

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Докажем по индукции.

База при предположим, что у каждой вершины не более двух рёбер, тогда всего рёбер не более но их хотя бы Значит некоторая вершина соединена с тремя остальными. Но тогда остальные не могут быть соединены между собой, но в этом случае будет не более трёх рёбер, противоречие. Значит, треугольник всё-таки есть.

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