18
правок
Изменения
Нет описания правки
{{Определение
|definition=
<tex> t_{r-1}(n) </tex> {{---}} количество ребер в <tex>T^{r-1}(n) = r_{r-1}(n); (1)</tex>.
}}
Для всех целых чисел <tex>r</tex>, <tex>n</tex>, где <tex>r > 1</tex>, любой граф <tex>G \nsubseteq K^r</tex> с <tex>n</tex> вершинами и <tex>ex(n, K^r)</tex> ребрами есть <tex>T^{r-1}(n)</tex>.
|proof=
Применим индукцию по <tex>n</tex>. При <tex>n \le r - 1</tex> имеем <tex>G = K^n = T^{r-1}(n)</tex>, что и утверждалось База доказана. Пусть теперь для шага индукции <tex>n \ge r</tex>.
Поскольку <tex>G</tex> реберно-максимален без подграфа <tex>K^r</tex>, то <tex>G</tex> содержит подграф <tex>K^r</tex>. Обозначит любой из них как <tex>K</tex>. По индукционному предположению <tex>G - K</tex> имеет не более <tex>t_{r-1}(n - r + 1)</tex> ребер, а любая вершина <tex>G - K</tex> имеет не более <tex>r - 2</tex> соседей в <tex>K</tex>. Следовательно,
<tex>||G|| \le t_{r-1}(n + r - 1) + (n - r + 1)(r - 2) + {r-1 \choose 2} = t_{r-1}(n)</tex>; (1)
равенство справа следует непосредственно из графа Турана <tex>T^{r-1}(n)</tex>.
[[Файл:Turan theorem induction step.png|400px|thumb|left|Шаг индукции]]
Поскольку <tex>G</tex> экстремален для <tex>K^r</tex> и <tex>T^{r-1}(n) \nsupseteq K^r</tex>, в (1) имеет место равенство. Таким образом, любая вершина из <tex>G - K</tex> имеет ровно <tex>r - 2</tex> соседа в <tex>K</tex> {{---}} точно также, как и вершины <tex>x_1, ..., x_{r-1}</tex> из самого <tex>K</tex>. При <tex>i = 1, ..., r-1</tex> пусть
<tex>V_i := \{v \in V(G) | vx_i \not\in E(G)\}</tex>
есть множество всех вершин <tex>G</tex>, чьи <tex>r - 2</tex> соседей в <tex>K</tex> {{---}} в точности вершины, отличный от <tex>x_i</tex>. Поскольку <tex>K^r \nsubseteq G</tex>, все множества <tex>V_i</tex> независимы и они разбивают <tex>V(G)</tex>. Следовательно, граф <tex>G</tex> является <tex>(r-1)</tex>-дольным. Так как <tex>T^{r-1}(n)</tex> - единственный <tex>(r-1)</tex>-дольный граф с <tex>n</tex> вершинами и максимальными числом ребер, наше утверждение, что <tex>G = T^{r-1}(n)</tex>, следует из предположения об экстремальности <tex>G</tex>.
}}
==См. также==
==Источники информации==
''Дистель, Рейнград.'' Теория графов: Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. — 166-170 стр. — ISBN 5-86134-101-X.
