а) Оценка. Выберем вершину A наибольшей степени n и рассмотрим подграф G, образованный вершинами, куда ведут рёбра из A. Ясно, что в этом подграфе рёбер нет. Каждая вершина, не входящая в G имеет степень не больше n, а выходящие из них рёбра – это все рёбра исходного графа. Таким образом, общее число рёбер исходного графа не превосходит  n(30 – n) ≤ 15².

  Пример. Разобьём 30 вершин на две группы по 15 и проведём все рёбра, соединяющие вершины из разных групп. Получился граф без треугольников с 225 рёбрами.   б) Оценка. Выберем вершину A наибольшей степени n и рассмотрим подграф G, образованный вершинами, куда ведут рёбра из A. Ясно, что в этом подграфе нет треугольников, поэтому, как фактически доказано в а), число его рёбер не превосходит (ⁿ/₂)². Таким образом, общее число рёбер исходного графа не превосходит  (n/₂)² + n(30 – n) = ³/₄ n(40 – n) ≤ ³/₄·20² = 300.

  Пример. Разобьём 30 вершин на три группы по 10 и проведём все рёбра, соединяющие вершины из разных групп. Получился граф без полных 4-подграфов с 300 рёбрами.

а) 225;  б) 300 рёбер.