Считаем рёбра

Предположим, что, если в графе есть треугольник, то ребер не больше для нечетных и для четных Выкинем вершины треугольника. Если в оставшемся графе есть хотя бы одно ребро, то взяв его концы и наш треугольник, мы получим вершин, из которых нельзя выбрать попарно не соединенные. Тогда все ребра графа имеют хотя бы один конец в вершине нашего треугольника. Причем из фиксированной вершины не могут вести ребра во все вершины нашего треугольника (иначе был бы полный граф на вершинах). Тогда ребер в этом случае не больше, чем при нечетных а также для четных А для мы получили оценку сверху на

Если же в графе нет треугольников, то максимум количества ребер будет достигаться в случае полного двудольного графа с одинаковыми долями для четного а для нечетного — с долями отличающимися на Легко видеть, что такие двудольные графы являются примерами с нужным количеством ребер для всех Если же то примером с ребрами будет конструкция из треугольников, имеющих одно общее ребро.