Найдите максимальное число рёбер в графе на 7 вершинах, не содержащем полного подграфа $K_{3}$ (треугольника). Какой граф реализует этот максимум? Используйте теорему Турана.
Правильный ответ
По теореме Турана: $ex(7, K_{3}) = t(7,2)$ — число рёбер в двудольном графе Турана $T(7,2)$. Разбиение на доли 3 и 4 даёт $3 \cdot 4 = 12$ рёбер. Граф — полный двудольный $K_{3,4}$. Это максимум.
💡 Авторизуйтесь, чтобы получить помощь AI-тьютора с подсказками и решениями!