[Math] Proof of Turan’s theorem

extremal-combinatoricsgraph theory

I'm following the proof of Turan's theorem on $\text{ex}(n,K^r)$ in Diestel's Graph Theory book (click to see the page) and something bothers me:

Since $G$ is edge-maximal without a $K^r$ subgraph, $G$ has a subgraph
$K=K^{r-1}$. By the induction hypothesis, $G-K$ has at most
$t_{r-1}(n-r+1)$ edges […]

But why would $G-K$ be $K^{r-1}-$free ? Couldn't there be other $K^{r-1}$ disjoint subgraphs in $G$ ?

Best Answer

The proof does not claim that $G-K$ is $K^{r-1}$-free, only that it is $K^r$-free. The induction is on $n$, not on $r$, so the assumption is that all smaller $K^r$-free graphs have been classified.

Related Question