Erdos (1970) proof of Turan’s Theorem – Applying induction on S

Question

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

Answer 1

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.