Theorem. The Turan graph $T_{n,r}$ maximizes the number of edges among all
$n$-vertex $K_{r+1}$-free graphs. It is also the unique maximizer.Proof. We fix $r$ and proceed by induction on $n$. The statement is trivial for $n\leq r$, as the Turan graph is the complete graph
$K_n=T_{n,r}$ and thus maximizes the number of edges.Now, assume that $n>r$ and that Turan's theorem holds for all graphs
on fewer than $n$ vertices. Let $G=(V,E)$ be an $n$-vertex
$K_{r+1}$-free graph with the maximum possible number of edges. By the
maximality assumption, $G$ contains $K_r$ as a subgraph, since
otherwise we could add an edge to $G$ and it would be still
$K_{r+1}$-free. Let $A$ be the vertex set of an $r$-clique in $G$, and
let $B:=V\setminus A$.
Since $G$ is $K_{r+1}$-free, every $x\in B$ has at most $r-1$
neighbors in $A$. So $$e(A,B)=\sum \limits_{y\in B}|N(y)\cap A|\leq
\sum \limits_{y\in B}(r-1)=(r-1)(n-r).$$ We have
$$e(G)=e(A)+e(A,B)+e(B)\leq
\dbinom{r}{2}+(r-1)(n-r)+e(T_{n-r,r})=e(T_{n,r}),$$ where the
inquality uses the induction hypothesis on $G[B]$, which is
$K_{r+1}$-free, and the final equality can be seen by removing a $K_r$
from $T_{n,r}$.Finally, let us check when equality occurs. To have equality in every
step above, the subgraph induced on $B$ must be $T_{n-r,r}$ by
induction. To have $e(A)=\dbinom{r}{2}$, $A$ must induce a clqiue. To
have $e(A,B)=(r-1)(n-r)$, every vertex of $B$ must be adjacent toa ll
but one vertex in $A$. Also, two vertices $x,y$ lying in distinct
parts of $G[B]\cong T_{n-r,r}$ cannot "miss" the same vertex $v$ of
$A$, or else $A\cup \{x,y\}\setminus \{v\}$ would be an
$K_{r+1}$-clique. This then forces $G$ to be $T_{n,r}$.
Question: I am a bit confused with the proof of uniqueness. We know that $G[A]\cong K_r$, $G[B]\cong T_{n-r,r}$ and $\forall y\in B \ (|N(y)\cap A|=r-1)$. Suppose that $V_1,\dots,V_r$ are the vertex parts of Turan graph $T_{n-r,r}$ and $|V_1|+\dots+|V_r|=n-r$.
Assume that $a,b\in V_1$ and we know that $|N(a)\cap A|=|N(b)\cap A|=r-1$. I was wondering is it true that $N(a)\cap A=N(b)\cap A$, i.e. are $N(a)$ and $N(b)$ missing the same vertex from $A$? I guess it should be true but it is not obvious to me.
Thanks a lot for your help!
Best Answer
For convenience, I'll refer to the second-to-last sentence of the proof you've posted as $\star$.
For each $b\in B$, let $a_b\in A$ be the unique element of $A$ not connected to $b$. Fact $\star$ now says precisely the $a_b\neq a_c$ for any $i\neq j$ and $b\in V_i,c\in V_j$.
Okay, now pick any $b_1\in V_1,\dots,b_r\in V_r$. By $\star$, we have $a_{b_i}\neq a_{b_j}$ for all $i\neq j$, whence $A=\{a_{b_1},\dots,a_{b_r}\}$. Now I claim that $N(b)\cap A=A\setminus\{a_{b_i}\}$ for all $i\in\{1,\dots,r\}$ and $b\in V_i$; this will show the desired result. If it were not the case, then there would be some $i$ and $c\in V_i$ such that $N(c)\cap A=A\setminus\{a_{b_j}\}$ for some $j\neq i$. But then $a_c=a_{b_j}$, contradicting fact $\star$, so we are done.
Once you've shown this, then you're done. Just to spell it out in detail: by the argument above, for each $i\in\{1,\dots,r\}$, there is a vertex $a_i\in A$ such that $a_i\notin N(b)$ for all $b\in V_i$. Let $W_i=V_i\cup\{a_i\}$; then $e(W_i)$ is empty for each $i$ by the definition of $V_i$ and $a_i$. Moreover, we know $G[V_i\cup V_j]$ is complete bipartite for $i\neq j$, and by fact $\star$ we have that $a_i$ is connected to every element of $V_j$ for $i\neq j$. So $G[W_i\cup W_j]$ is complete bipartite, as needed.