Turan’s Theorem

The Turan number $\text{ex}(n,K_r)$ is uniquely achieved by the complete $(r-1)$-partite graph with parts of size

$$\lfloor \frac{n}{r-1}\rfloor \text{ or }\lceil \frac{n}{r-1}\rceil$$

In particular, the extremal graph is denoted as $T_{n,r}$.

Proof:

First, we want to prove that

$$\text{ex}(n,K_r)=|E(T_{n,r})|$$

by induction on $n$.

Base Case: If $n=r-1$ we are done since we have $K_{r-1}$, and clearly $K_r$ does not exist.

Inductive Step: We WTS that if $G$ has no $K_r$, then $\delta (G)\le n-\lceil n/(r-1)\rceil$. If such a vertex $v$ had this minimal degree, then by removing $v$,

$$\begin{array}{rlrl}\text{ex}(n,K_r)& \le n-\lceil n/r-1\rceil +\text{ex}(n-1,K_r)& & \\ & =n-\lceil n/r-1\rceil +|E(T_{n-1,r})|& & \leftarrow \text{by IH}\\ & =|E(T_{n,r})|& & \end{array}$$

in the last step, we add back $v$. Since $\mathrm{deg}(v)=n-\lceil n/(r-1)\rceil$, then adding those edges back gives us $T_{n,r}$. Notice how the total number of vertices not in $v$‘s partition is exactly the upper bound of $\delta (G)$.

Now assume for sake of contradiction that $\delta (G)>n-\lceil n/(r-1)\rceil$. The goal is to find $K_r$. So let’s start with $n$ vertices and pick a vertex $v_1$ to be in $K_r$. Let’s discard (or ignore) the non neighbors of $v_1$. In particular, we have not discarded many vertices. Since $\delta (G)$ is high, then we removed

$$\text{Removed}=n-\mathrm{deg}(v)<n-\left(n-\lceil \frac{n}{r-1}\rceil \right)=\frac{n}{r-1}$$

Then we will pick a $v_2\in N(v_1)$ and discard the non neighbors of $v_2$ and repeat. Each selected vertex must be adjacent to every previously selected vertex. At the end, we end up with a complete graph.

The point is that on any round, the vertex selected and its non neighbors is going remove fewer than $n/(r-1)$ vertices. So after $k$ rounds, we have strictly more than

$$n-\frac{kn}{r-1}$$

vertices left. After $r-1$ rounds, there is strictly

$$n-\frac{(r-1)n}{r-1}=n-n=0$$

left. Indeed, $>0⟺\ge 1$, so this is at least one more vertex to select. But as each vertex selected is adjacent to every other vertex selected, we get $K_r$.

To prove $G$‘s uniqueness, if $G$ is an extremal graph, then it must isomorphic to $T_{n,r}$. Suppose so. Then by the previous work,

$$|E(G)|=\text{ex}(n,K_r)=|E(T_{n,r})|$$

We proceed by induction. I claim that

$$\delta (G)=n-\lceil \frac{n}{r-1}\rceil \mathrm{deg}(v)=\delta (G)⟹|E(G-\{v\})|=|E(T_{n-1,r})|$$

and that removing $v$ where $\mathrm{deg}(v)=\delta (G)$ gives us the Turan graph. From our previous work,

1. If $G$ has no $K_r$ then $\delta (G)\le \delta (T_{n,r})$.
2. $|E(T_{n,r})|=\delta (T_{n,r})+|E(T_{n-1,r})$ This gives us

$$\begin{array}{rl}\mathrm{deg}(v)+|E(G-v)|& =|E(G)|\\ & =|E(T_{n,r})\\ & =\delta (T_{n,r})+|E(T_{n-1,r})|\end{array}$$

As $\mathrm{deg}(v)=\delta (G)\le \delta (T_{n,r})$ and $|E(G-v)|\le |E(T_{n-1,r})|$, then equality can only be achieved if pairwise, the terms are equal. Thus

$$\delta (G)=\delta (T_{n,r})=n-\lceil \frac{n}{r-1}\rceil$$

Since $|E(G-v)|=|E(T_{n-1,r})|$ and that $G-v$ has no $K_r$, by the induction hypothesis on uniqueness, $G-v$ is uniquely isomorphic to $T_{n-1,r}$.

Let $V_1,V_2,\dots ,V_{r-1}$ be the partitions of the complete $(r-1)$-partite graph of $G-v$. The goal is to add back $v$, and show that doing so gives us $T_{n,r}$. In particular,

1. $v$ cannot be adjacent to some vertex in every $V_i$. Otherwise, as these $r-1$ vertices already connect to each other, then we have $K_{r-1}\subset G-v$. Thus, adding $v$ gives $K_r$, a contradiction.
2. So adding $v$ means we connect to every part except one partition. Since $\mathrm{deg}(v)=\delta (T_{n,r})$, then $$\mathrm{deg}(v)\le \left(\sum _{i\ne k}|V_i|\right)=(n-1)-|V_k|$$
3. Since $v$ is minimal then it must be from the largest possible partition $V_{\text{max}}$. Thus, $$\delta (T_{n,r})=(n-1)-|V_{\max }|$$
4. This gives us $$\begin{array}{rl}\mathrm{deg}(v)& \le (n-1)-|V_k|\\ (n-1)-|V_{\max }|& \le (n-1)-|V_k|\\ |V_k|& \le |V_{\max }|\end{array}$$ So, $v$ must be be connected to every vertex in every partition but $V_k$.
5. $V_k\cap N(v)=\varnothing$ means that we can add $v$ to $V_k$ while respecting the partition structure of $G$. Thus, $G$ is complete $(r-1)$-partite graph with $V_1,\dots ,V_k\cup \{v\},\dots ,V_{r-1}$. As $|E(G)|=\text{ex}(n,K_r)$, $G$ is the unique extremal graph, and edge count is maximized when all sizes are as equal as possible. Thus $G\cong T_{n,r}$.