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

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

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

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

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

[math]ex(n, K^r)[/math] — максимальное количество ребер в графе на [math]n[/math] вершинах, которые не содержит [math]K^r[/math] как подграф.

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

Граф Турана [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].

Пример графа Турана

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

[math] t_{r-1}(n) [/math] — количество ребер в [math]T^{r-1}(n) = r_{r-1}(n); (1)[/math].

Теорема:

Для всех целых чисел [math]r[/math], [math]n[/math], где [math]r \gt 1[/math], любой граф [math]G \nsubseteq K^r[/math] с [math]n[/math] вершинами и [math]ex(n, K^r)[/math] ребрами есть [math]T^{r-1}(n)[/math].

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

[math]\triangleright[/math]

Применим индукцию по [math]n[/math]. При [math]n \le r - 1[/math] имеем [math]G = K^n = T^{r-1}(n)[/math], что и утверждалось База доказана. Пусть теперь для шага индукции [math]n \ge r[/math]. Поскольку [math]G[/math] реберно-максимален без подграфа [math]K^r[/math], то [math]G[/math] содержит подграф [math]K^r[/math]. Обозначит любой из них как [math]K[/math]. По индукционному предположению [math]G - K[/math] имеет не более [math]t_{r-1}(n - r + 1)[/math] ребер, а любая вершина [math]G - K[/math] имеет не более [math]r - 2[/math] соседей в [math]K[/math]. Следовательно, [math]||G|| \le t_{r-1}(n + r - 1) + (n - r + 1)(r - 2) + {r-1 \choose 2} = t_{r-1}(n)[/math]; (1) равенство справа следует непосредственно из графа Турана [math]T^{r-1}(n)[/math]. Шаг индукции Поскольку [math]G[/math] экстремален для [math]K^r[/math] и [math]T^{r-1}(n) \nsupseteq K^r[/math], в (1) имеет место равенство. Таким образом, любая вершина из [math]G - K[/math] имеет ровно [math]r - 2[/math] соседа в [math]K[/math] — точно также, как и вершины [math]x_1, ..., x_{r-1}[/math] из самого [math]K[/math]. При [math]i = 1, ..., r-1[/math] пусть [math]V_i := \{v \in V(G) | vx_i \not\in E(G)\}[/math] есть множество всех вершин [math]G[/math], чьи [math]r - 2[/math] соседей в [math]K[/math] — в точности вершины, отличный от [math]x_i[/math]. Поскольку [math]K^r \nsubseteq G[/math], все множества [math]V_i[/math] независимы и они разбивают [math]V(G)[/math]. Следовательно, граф [math]G[/math] является [math](r-1)[/math]-дольным. Так как [math]T^{r-1}(n)[/math] - единственный [math](r-1)[/math]-дольный граф с [math]n[/math] вершинами и максимальными числом ребер, наше утверждение, что [math]G = T^{r-1}(n)[/math], следует из предположения об экстремальности [math]G[/math].

[math]\triangleleft[/math]

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

Дистель, Рейнград. Теория графов: Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. — 166-170 стр. — ISBN 5-86134-101-X.