Erdos (1970) proof of Turan's Theorem - Applying induction on S I am following "Turan's Graph Theorem" by M. Aigner. In the second proof by Erdos, he states,

"Applying induction on S, we thus infer that among the graphs with a maximal number of edges there is a graph $K_{n_1,...,n_{k-1}}$"

is where I get confused with the proof. What does he mean by induction on S? I feel as I need help with the steps between the construction of H, how it gives the upperbound for edges of G (i.e $|E(H)|\geq|E(G)|$) , and how by "induction on S" we know there's a Turan graph among the graphs with maximal edges (also, does this imply that graph H is that Turan graph-if so, what guarantees it?).
Thank you
 A: In this case, "Applying induction on $S$" means "Applying the $k-1$ case of the theorem to the subgraph $G[S]$".
Formally, the theorem we're proving here is the following version of Turán's theorem:

Theorem. For all $n,k$, if $G$ is an $n$-vertex graph with no $k$-clique, then there is a $(k-1)$-partite $n$-vertex graph with at least as many edges as $G$.

Going through all the things you want help with:
The construction of $H$. We let $m$ be a vertex in $G$ with the largest degree; $S$ is the set of neighbors of $m$, and $T$ is the complement of $S$ (so $m \in T$). To get $H$ from $G$, we:

*

*Delete all edges within $T$ (if there were any);

*Add all missing edges between $S$ and $T$ (if there were any).

Why is $|E(H)| \ge |E(G)|$? We prove a stronger statement: for all vertices $v$, $\deg_H(v) \ge \deg_G(v)$. This gives us an inequality between the edge counts, since the sum of degrees gives us twice the number of edges.
We check the degree inequality separately in two cases:

*

*Suppose $v \in S$. In this case, going from $G$ to $H$, we did not delete any edges out of $v$, but possibly we added some edges (if $v$ was not already adjacent to all of $T$). So we can only increase the degree of $v$.

*Suppose $v \in T$. In this case, the degree of $v$ in $H$ is $|S|$, since $H$ contains all edges between $S$ and $T$. In $G$, the degree of $v$ was at most the degree of $m$ (by our choice of $m$), so it was at mot $|S|$.

How does the induction work? It is an induction on $k$. The base case can be $k=2$: the only graph with no $2$-cliques (edges) is the empty graph, which is a $1$-partite graph.
If $G$ started out as a graph with no $k$-cliques, then the subgraph $G[S]$ must be a subgraph with no $(k-1)$-cliques (any $(k-1)$-clique in $G[S]$ would form a $k$-clique together with $m$). By induction, there is some $(k-2)$-partite graph $K$ on $|S|$ vertices with $|E(K)| \ge |E(G[S])|$.
Now modify $H$ by replacing $G[S]$ (or $H[S]$, which is the same thing) with the $(k-2)$-partite graph $K$. The result (call it $H'$)

*

*Still has at least as many edges as $G$: the number of edges did not decrease when going from $G$ to $H$, and it did not decrease when replacing $G[S]$ with $K$.

*Is $(k-1)$-partite. Since $K$ is a $(k-2)$-partite graph on $S$, there is a partition $S = S_1 \cup S_2 \cup \dots \cup S_{k-2}$ such that $K$ has no edges inside any $S_i$. Also, $H$ has no edges inside $T$, because we deleted them all. So $H'$ has a vertex partition $S_1 \cup S_2 \cup \dots \cup S_{k-2} \cup T$ with no edges inside any part: this is the definition of a $(k-1)$-partite graph.

This proves the theorem.
