Теорема Турана об экстремальном графе

Теорема Турана

Теорема Ту́рана дает сверху на количество ребер в графе, в котором нет полного n-дольного подграфа. Это классическая теорема из экстремальной теории графов. Она послужила образцом для большого количества подобных теорем, которые оценивают некоторые глобальные параметры, такие как хроматическое число, относительно тех или иных подструктур.

Впервые задачу сформулировал Пал Туран в 1941 году.

Источники информации

• Книга по дискре