Изменения

[[Файл:Turan example.png|200px|thumb|right|Пример графа Турана при <tex>n = 8, r = 4</tex>]]'''Теорема Ту́рана''' (англ. ''Turán's theorem'') {{---}} классическая теорема экстремальной теории графов. Она послужила образцом для большого количества подобных теорем, которые изучают некоторые глобальные параметры, такие как [[Раскраска графа| хроматическое число]], относительно присутствия тех или иных подструктур.

'''Граф Турана''' <tex>T^{r-1}(n)</tex> {{---}} единственный полный <tex>(r - 1)</tex>-дольный полный граф на <tex>n > r-1</tex> вершинах, доли которого по мощности не отличаются более чем на 1. Если <tex>n \leqslant r - 1</tex>, то <tex>T^{r-1}(n) = K^n</tex>. Через <tex> t_{r-1}(n) </tex> обозначим количество ребер в <tex>T^{r-1}(n)</tex>.}} [[Файл:Turan example.png|thumb|left|Пример графа Турана]]

 {{ОпределениеЛемма|definitionstatement=Среди <tex> t_{(r-1}(n) </tex> {{---}} количество ребер в дольных графов <tex>T^{r-1}(n) </tex> имеет максимальное количество ребер.|proof= r_{Пусть есть существует максимальный <tex>(r-1}(n); (</tex>-дольный граф, в котором есть две доли <tex>V_1 и V_2 \ | \ |V_1| - |V_2| > 1)</tex>.Но тогда перекинув одну вершину из <tex>V_1</tex> в <tex>V_2</tex>, количество ребер увеличится. Противоречие.

Применим индукцию по <tex>n</tex>. При <tex>n \le r - 1</tex> имеем <tex>G = K^n = T^{r-1}(n)</tex>, что и утверждалось База доказана. Пусть теперь для шага индукции <tex>n \ge r</tex>.

Пусть теперь <tex>n \ge r</tex>.Поскольку <tex>G</tex> реберно-максимален и не содержит подграфа <tex>K^r</tex>, то <tex>||G|| \le t_</tex> содержит подграф <tex>K^{r-1}(n + </tex>. Обозначим любой из них как <tex>K</tex>. Тогда индукционному предположению <tex>G - K</tex> имеет не более <tex>t_{r - 1) + }(n - r + 1)(r </tex> ребер, а любая вершина <tex>G - 2) + {K</tex> имеет не более <tex>r-1 \choose 2} = t_{r-1}(n)</tex>; (1)соседей в <tex>K</tex>. Следовательно:

равенство справа следует непосредственно из графа Турана <tex>T^|E(G)| \le \underbrace{t_{r-1}(n + r-1)}_{G-K}+ \underbrace{(n- r + 1)(r - 2)}_{(G-K) \rightleftarrows (K)} + \underbrace{{r-1 \choose 2}}_{K} = t_{r-1}(n); (1)</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>G</tex> экстремален для <tex>K^r</tex>, то в <tex>V_i := \{v \in V(G1) | vx_i \not\in E(</tex> имеет место равенство. Таким образом, любая вершина из <tex>G)- K</tex> имеет ровно <tex>r - 2</tex> соседа в <tex>K</tex> {{---}} точно также, как и вершины <tex>x_1,\cdots, x_{r-1}</tex>из самого <tex>K</tex>.

При <tex>i = 1,\cdots, 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>G - K^</tex> имеет ровно <tex>r \nsubseteq G- 2</tex> соседа в <tex>K</tex>, то все множества <tex>V_i</tex> независимы и не зависимы. При этом они разбивают в объединении дают <tex>V(G)</tex> поскольку <tex>K^r \nsubseteq 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>.