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.