Lemma 1.2.7. Among $n$-vertex $r$-partite graphs, $T_{n,r}$ is the unique graph with the maximum number of edges.
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. As before, let $G$ be an $n$-vertex, $K_{r+1}$-free graph with the maximum possible number of edges.
We claim that if $x$ and $y$ are non-adjacent vertices, then $\deg
x=\deg y$. Indeed, suppose $\deg x>\deg y$. We can modify $G$ by
removing $y$ and adding in a clone of $x$ (a new vertex $x'$ with the
same neightborhood as $x$ but not adjacent to $x$), as illustrated
below.
The resulting graph would still be $K_{r+1}$-free (since a clique
cannot contain both $x$ and its clone) and has strictly more edges
than $G$, thereby contradicting the assumption that $G$ has the
maximum possible number of edges.Suppose $x$ is non-adjacent to both $y$ and $z$ in $G$. We claim that
$y$ and $z$ must be non-adjacent. We just saw that $\deg x=\deg y=\deg
z$. If $yz$ is an edge, then by deleting $y$ and $z$ from $G$ and
adding two clones of $x$, we obtain a $K_{r+1}$-free graph with one
more edge than $G$. This would contradict the maximality of $G$.
Therefore, non-adjacency is an equivalence relation among vertcies of
$G$. So the complememnt of $G$ is a union of cliques. Hence $G$ is a
complete multipartite graph, which has at most $r$ parts since $G$ is
$K_{r+1}$-free. Among all complete $r$-partite graphs, the Turan graph
$T_{n,r}$ is the unique graph that maximizes the number of edges, by
Lemma 1.2.7. Therefore, $G$ is isomorphic to $T_{n,r}$.
I understand the general idea of the proof but I'd like to clarify some moments.
Question 1. Assume that $V(G)=\{v_1,\dots,v_n\}$. The relation $v_i\sim v_j \Leftrightarrow v_iv_j\notin E(G)$ is an equivalence realtion on $V(G)$. Since any equivalence relation on set forms its partition, then $V(G)=V_1\sqcup \dots\sqcup V_N$, where $V_i$ are equivalence classes. More precisely, each $V_i$ is an independent set and for any $a\in V_i$, $b\in V_j$ with $i\neq j$ there is an edge connecting $a$ and $b$. It means that $G$ is complete $N$-partite graph. Is my reasoning correct here? I do not see the point why the author says that the complement of graph is a bunch of cliques.
Question 2. We know that initially $G$ is $n$-vertex, $K_{r+1}$-free graph with the maximum number of edges and we were able to show $G$ is complete, $N$-partite graph with $N\leq r$. I am confused how the author used the Lemma to show that $G=T_{n,r}$. How to show that $N=r$ and only in this case it has the maximum number of edges?
I'd be really thankful for help! Thank you so much!
Best Answer
Question 1) Yes. You are correct. It's maybe a bit easier visually to think of cliques as being equivalence classes (and is a common example to think about), so that may be why the author chose to phrase it in terms of complement.
Question 2) The main theorem proof shows that $G$ is $r$-partite. As pointed out by jacob in the comments - this means it has at most $r$ maximal independent sets. As you've noticed, it could in theory have fewer from the proof thus far.
What the Lemma is really saying, with this understanding of what $r$-partite means is: among all $n$-vertex complete multipartite graphs with $r$ or fewer partite sets, $T_{n,r}$ is the unique edge maximiser. We know $G$ is $r$-partite with $n$ vertices, and maximises the edge count, so it is $T_{n,r}$ by the Lemma. I.e., the Lemma tells you $N=r$.