Воспользуемся теоремой Тюрана для $r=2$: максимальное число рёбер в графе без треугольника на $n$ вершинах равно ⌊$\frac{n^{2}}{4}$⌋. При $n=10$ это ⌊$\frac{100}{4}$⌋ = 25. Прямое доказательство: пусть вершина $v$ имеет степень $d(v)$. Её соседи не соединены между собой (иначе треугольник). Каждое ребро не инцидентно $v$ соединяет вершину-соседа $v$ с не-соседом. Суммируя по вершинам и применяя неравенство, получаем $|E| \leq \frac{n^{2}}{4} = 25$.

💡 Авторизуйтесь, чтобы получить помощь AI-тьютора с подсказками и решениями!