Изменения

Пусть есть существует максимальный <tex>(r - 1)</tex>-дольный граф, в котором есть две доли <tex>V_1 </tex> и <tex>V_2 \ | \ </tex>, такие что <tex>|V_1| - |V_2| > 1</tex>. Но тогда перекинув одну вершину из <tex>V_1</tex> в <tex>V_2</tex>, количество ребер увеличится. Противоречие.

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

Поскольку <tex>G</tex> реберно-максимален и не содержит подграфа <tex>K^r</tex>, то <tex>G</tex> содержит подграф <tex>K^{r-1}</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</tex>:

<tex>|E(G)| \le leqslant \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>

Поскольку <tex>G</tex> экстремален для <tex>K^r</tex>, то в <tex>(1)</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)\ |\ mid vx_i \not\in E(G)\}</tex> есть множество всех вершин <tex>G</tex>, чьи <tex>r - 2</tex> соседей в <tex>K</tex> отличны от <tex>x_i</tex>.