Лемма Турана

Наибольшее число ребер у графов, имеющих n вершин и не содержащих треугольников, равно [n^2/4].

Это утверждение обычно называют леммой Турана, хотя оно было доказано французом Мантелем на тридцать лет раньше.

Доказательство 1 проведем по индукции. База очевидна.
Рассмотрим здесь случай четных n.

Предположим, что утверждение справедливо для всех четных n<=2m (для нечётных доказывается аналогично).

Докажем его для n=2m+2. Итак, пусть G - граф с n=2m+2 вершинами, не содержащий треугольников. Поскольку граф G не является пустым, то в нем существуют две смежные вершины u и v. Удалим эти вершины со всеми выходящими из них ребрами, получим граф G', в котором 2m вершин и нет треугольников, так что по предположению индукции в нем не более m^2 ребер. Сколько еще ребер может быть в G? В графе нет такой вершины w, которая смежна и с u, и с v. Таким образом, если вершина u смежна с k вершинами графа G', то вершина v смежна самое большее с 2m-k вершинами. Поэтому в графе G не более, чем m^2+k+(2m-k)+1=[n^2/2] ребер.

Для завершения доказательства осталось установить, что для каждого n существует граф с [n^2/4] ребрами. В случае четного n это полный двудольный граф, где в каждой доле по n/2 вершин, а в случае нечетного n - полный двудольный граф, где в одной доле (n+1)/2 вершин, а в другой -(n-1)/2 вершин.

Доказательство 2. Выберем вершину максимальной степени, пусть ее степень равна k. Любые две вершины, смежные ей, не смежны, так как в противном случае образовался бы треугольник.

Рассмотрим несмежные с ней n-k-1 вершину. Максимальное число ребер, из них выходящих, равна (n-k-1)k, причем в этом случае они не соединены между собой. Следовательно, ребер в графе не более k+(n-k-1)k=k(n-k). Далее максимизируем по k...