Граф Турана $T(n,2)$ — полный двудольный граф с долями $\lfloor \frac{n}{2} \rfloor$ и $\lceil \frac{n}{2} \rceil$. Число рёбер: $\lfloor n^\frac{2}{4} \rfloor$. Он не содержит треугольника (двудольный), и добавление любого ребра создаёт треугольник. По теореме Турана это единственный экстремальный граф.

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