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

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

Теорема Ту́рана (англ. Turán's theorem) — классическая теорема экстремальной теории графов. Она послужила образцом для большого количества подобных теорем, которые изучают некоторые глобальные параметры, такие как хроматическое число, относительно присутствия тех или иных подструктур.

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

Определение:

[math]T^{r-1}(n)[/math] — единственный полный [math](r - 1)[/math]-дольный полный граф на [math]n \gt r-1[/math] вершинах, доли которого по мощности не отличаются более чем на 1. Если [math]n \leqslant r - 1[/math], то [math]T^{r-1}(n) = K^n[/math].

Определение:

ex(n, r) — количество ребер в T^r(n).

Теорема:

Для всем целых чисел r, n, где r > 1, любой граф G >= K^r с n вершинами и ex(n, K^r) ребрами есть T^r-1(n)

Доказательство:

[math]\triangleright[/math]

доказательство (необязательно)

[math]\triangleleft[/math]

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

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