(это лемма Турана) В графе 2n вершин и n^2+1 ребро. Обосновать,

Построим таблицу 2n2n (см. рис). Столбцы и строчки означают верхушки (они занумерованы числами от 1 до 2n). Если какие-то верхушки соединены ребром, то на подходящем пересечении столбца и строки напишем 1. К примеру, если верхушки 4 и 2 соединены ребром, то на скрещении 4 столбца и 2 строчки напишем 1. Так как 4 столбец и 4-ая строка отвечают за одну и ту же верхушку, можем отрезать таблицу пополам (по полосы диагонали). Заметим, если три верхушки образуют треугольник, то единицы, соответствующие этим соединениям образуют прямоугольный треугольник (если мысленно их соединить в таблице). Также, хоть какой двойке единиц в конкретном столбце подходит единственная единица в подходящей строке, такая что они втроем образуют треугольник. Например, на рисунке красноватые единицы образуют треугольные, а голубые - нет. При этом двойке красных единиц в 4-ом столбце подходит единственная 1-ца, такая, что они совместно образуют треугольник (если бы 3-я единица была в 3-ем столбце, 1 строке, то треугольник не создавался). Означает общее число треугольников в графе подходит сумме комбинаций двоек в каждом столбце. Пусть в первом столбце n единиц, во втором n и т.д. Означает общее число треугольников одинаково (*); Заметим, что малое значение выражения A-A для естественных чисел одинаково 1. Раз  , то с учетом (*), малое количество треугольников равно 2n/2 = n; То есть светло, что желая бы один треугольник появляется