How to ensure that each part of $G$ differs at most one vertex in the proof of Turan theorem? In Diestel's Graph Theory, I try to figure out the proof of Theorem 7.1.1 (Turan theorem) on page 165:

For all integers $r, n$ with $r>1$, every $K_r$-free graph $G$ (i.e., $G$ does not have the $r-$complete graph $K_r$ as a subgraph) on $n$ vertices and $ex(n, K_r)$ (i.e., the maximum number of edges so that $G$ is $K_r$-free) is a $T^{r-1}(n)$. Here $T^{r-1}(n)$ is called Turan graph which is a unique $(r-1)-$multipartite graph with each parts differ at most one vertex.

I try to understand the first proof by induction and I am not sure if I understand it right.
Here we prove it by induction on $n$. Since $n\le r-1$ is a trivial case, $T^{r-1}(n)=K_{r-1}$ which is $K_r$-free as claimed.
For $n\ge r$, we assume that $G$ on the number of vertices $n$ is true (or say $n\le k$ is true), then we want to verify $n+1$ is also true (i.e., check $n=k+1$ holds).  Since $G$ is $K_{r}$-free, then it contains a subgraph $K_{r-1}$ (by the edge-maximal property).
Consider the graph $G-K_{r-1}$ that removes a subgraph $K_{r-1}$. Note that we count the number of edges of $G$ from three sources: the edges inside $K_{r-1}$, the edges between $K_{r-1}$ and $G-K_{r-1}$, and the edges inside $G-K_{r-1}$. So we upper bound the number of edges of $G$
$$
||G||\le \tbinom{r-1}{2}+(n-r+1)(r-2)+t_{r-1}(n-r+1)=t_{r-1}(n) --- (*)
$$
where the second term is because each vertex in $G-K_{r-1}$ has at most $r-2$ neighbors in $K_{r-1}$ (otherwise, there would be a $K_r$ subgraph in $G$), and the third term follows from the induction hypothesis since $n-r+1<n$. Since each part in $T^{r-1}(n)$ differs at most one vertex, we remove at most one vertex in each part for $G-K_{r-1}$. So the last equality holds.
Since $G$ is the extremal case on $n$ vertices, so the number of edges of $G$ is just equal to $t_{r-1}(n)$. Thus, the neighbors of each vertex of $G-K_{r-1}$ in $K_{r-1}$ is just $r-2$.
Then we need to show that such $G$ is just $T^{r-1}(n)$.
[I am not very sure what the author means in the following proof]
Consider $V(K_{r-1})=\{x_1,\dots, x_{r-1}\}$. Let
$$
V_i=\{v\in V(G): vx_i\notin E(G)\}, i=1,\dots, r-1
$$
be the set of all vertices of $G$ whose $r-2$ neighbors in $K_{r-1}$ are precisely the vertices other than $x_i$.
Note that each set $V_i$ is independent for all $i=1,\dots, r-1$ (because $G$ is $K_r$-free). Also, since $V_i$'s are independent and partition $V(G)$, then $G$ is $(r-1)$-partite. As $T^{r-1}(n)$ is the unique $(r-1)$-partite graph. Then we conclude that $G=T^{r-1}(n)$.
Question: How to ensure that each part of $G$ differs at most one vertex on the above construction? [Since the definition of $T^{r-1}(n)$ is the unique $(r-1)$-partite graph with each part differing at most 1 vertex].
 A: At this point in the proof, we don't yet know the sizes of $V_1, \dots, V_{r-1}$; all we know is that they're independent sets and that they partition $V(G)$.
To prove more, we use the assumption that $G$ is a $K_r$-free graph with as many edges as possible. This tells us that:

*

*$G$ must contain all the edges between different $V_i$'s, because adding those edges can't create a $K_r$. Therefore $G$ is a complete $(r-1)$-partite graph.

*We can't have $|V_i| \ge |V_j| + 2$ for any $i,j$, because moving a vertex from $V_i$ to $V_j$ would increase the number of edges by $|V_i|-|V_j|-1 > 0$. Therefore $G$ is a nearly balanced complete $(r-1)$-partite graph.

The reason Diestel doesn't spell out point 2 is because the argument was already given right before the definition of $T_{r-1}(n)$.

Another possible argument would use the inductive hypothesis to argue that $G-K$ is isomorphic to $T_{r-1}(n-r+1)$. We can check that $V_1 - \{x_1\}, \dots, V_{r-1} - \{x_{r-1}\}$ are an $(r-1)$-partition of $G-K$, so it must be the case that the sizes $|V_1 - \{x_1\}|, \dots, |V_{r-1} - \{x_{r-1}\}|$ differ by at most $1$. Each of those sizes is one less than the corresponding size $|V_1|, \dots, |V_{r-1}|$, so these also differ by at most $1$.

As for the upper bound
$$
   \|G\| \le \binom{r-1}{2} + (n-r+1)(r-2) + t_{r-1}(n-r+1),
$$
it follows from counting the edges from three places: there are $\binom{r-1}{2}$ edges in $K$, at most $(n-r+1)(r-2)$ edges between $G-K$ and $K$ (since every one of the $n-r+1$ vertices outside $K$ has at most $r-2$ neighbors in $K$), and at most $t_{r-1}(n-r+1)$ edges outside $K$ (by induction, since $G-K$ is a $K_r$-free, $(n-r+1)$-vertex graph).
This upper bound is equal to $t_{r-1}(n)$, because if we take $T_{r-1}(n-r+1)$ and increase the size of each part by $1$, we both

*

*Add exactly $\binom{r-1}{2} + (n-r+1)(r-2)$ new edges, and

*Obtain exactly $T_{r-1}(n)$.

