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.
