The Turán graph $T_{n,r}$ is defned to be the complete $n$-vertex,
$r$-partite graph with part sizes differing by at most $1$ (so each
part has size $\lfloor n/r\rfloor$ or $\lceil n/r \rceil$).Lemma 1.2.7. Among $n$-vertex $r$-partite graphs, $T_{n,r}$ is the unique graph with the maximum number of edges.
Proof. Suppose we have an $n$-vertex $r$-partite graph with the maximum possible number of edges. It should be a complete $r$-partite
graph. If there were two vertex parts $A$ and $B$ with $|A|+2\leq
|B|$, then moving a vertex from $B$ (the larger part) to $A$ (the
smaller part) would increase the number of edges by
$(|A|+1)(|B|-1)-|A||B|=|B|-|A|-1>0$. Thus all the vertex parts must
have sizes within one of each other. The Turán graph $T_{n,r}$ is the
unique such graph.
The statement of the lemma says that $\max \mathcal{C}=e(T_{n,r})$, where $\mathcal{C}=\{e(G): (G\ \text{has}\ n\ \text{vertices})\land (G\ \text{is}\ r\ \text{-partite})\}$.
But the proof actually shows that if $G\neq T_{n,r}$, then $G$ is not a maximizer. Of course it does not prove that $\max \mathcal{C}\leq e(T_{n,r})$.
Can anyone explain to me the reasoning behind the proof of this lemma, please?
Thank you!
Best Answer
Given a finite set $S$, a function $f:S\to \Bbb{R}$ and a proof that $s_0\in S$ satisfies $$ \forall s\in S, \ s\neq s_0 \implies \exists s'\in S \text{ s.t.} f(s')> f(s), $$ then $s_0$ is the unique maximizer of $f$ on $S$.
The proof is as follows. Take $s_1$ to be an arbitrary maximizer of $f$ on $S$ (existence follows from the finiteness of $S$). If $s_1 \neq s_0$ then it is not a maximizer, contradiction. Thus the only maximizer of $f$ on $S$ is $s_0$.
In the Turán case: the maximizer must exist, and cannot be anything other than the Turán graph.