What we will prove is that the maximum number of edges in a
\(K_r\)-free graph is attained by a complete
\((r-1)\)-partite graph; the fact that all of the parts have nearly the same size is a simple optimization (see
Exercise 12 in
Section 3.6).
Given a graph \(G\) and a vertex \(v\in V(G)\text{,}\) let \(G*v\) be the graph obtained from \(G\) by adding a new vertex, say \(v'\text{,}\) and adding an edge from \(v'\) to every neighbour of \(v\text{.}\) We call this operation cloning the vertex \(v\text{.}\) The proof relies on the following claim.
Claim 3.2.4.
Let \(G\) be a graph and \(v\in V(G)\text{.}\) If \(G\) is \(K_r\)-free and, then so is \(G*v\text{.}\)
Proof.
Let \(G\) be a \(K_r\)-free graph on \(n\) vertices with the maximum possible number of edges. Let \(u\) and \(v\) be a pair of non-adjacent vertices such that \(\degree(v)\geq \degree(u)\text{.}\) Consider the graph
\begin{equation*}
G'= (G-u)*v\text{.}
\end{equation*}
If you jettison a vertex from a
\(K_r\)-free graph, then it remains
\(K_r\)-free; thus,
\(G-u\) is
\(K_r\)-free. So, by
Claim 3.2.4,
\(G'\) is
\(K_r\)-free, too. Since
\(u\) and
\(v\) are not adjacent, the number of edges in
\(G'\) is
\(|E(G)|-\degree(u)+\degree(v)\text{.}\) Thus, by our choice of
\(G\text{,}\) it must hold that
\(\degree(v)=\degree(u)\text{;}\) so, any two non-adjacent vertices have the same degree.
Now, suppose that there is a triple of vertices \(u,v,w\) such that \(uv,
vw\notin E(G)\) and \(uw\in E(G)\text{.}\) By the result of the previous paragraph, we have that \(\degree(u)=\degree(v)=\degree(w)\text{.}\) Let
\begin{equation*}
G''= ((G-u-w)*v)*v\text{.}
\end{equation*}
This is a \(K_r\)-free graph with the number of edges equal to
\begin{equation*}
|E(G)|- d(u) - (d(w)-1) +2d(v) = |E(G)|+1
\end{equation*}
(since, after deleting \(u\text{,}\) the degree of \(w\) decreases by one, but the degree of \(v\) is not affected by deleting \(u\) or \(w\)). This contradicts our choice of \(G\text{;}\) thus, no triple of this type can exist.
From the previous paragraph, we see that no two vertices in the same component of the complement \(\overline{G}\) of \(G\) can be at distance greater than one from one another (otherwise, the closest such vertices are at distance two, which gives us a triple as in the previous paragraph). Therefore, \(G\) is a complete multipartite graph.