Skip to main content

Section 3.2 The Extremal Numbers of General Cliques

Next, let us consider the problem of determining \(\ex(n,K_r)\) for general \(r\text{.}\) The following is the natural generalization of the tight construction for Mantel’s Theorem.
described in detail following the image
“A dense graph.”

Example 3.2.1.

For \(k\geq1\text{,}\) a complete k-partite graph is a graph such that the vertex set can be partitioned into \(k\) sets \(A_1,\dots,A_k\text{,}\) called part s, such that there is an edge from every \(u\in A_i\) to every \(v\in A_j\) for \(i\neq j\text{,}\) but there are no edges between vertices of \(A_i\text{.}\) We denote this graph by completemultip where \(a_i=|A_i|\) for \(1\leq i\leq k\text{.}\)
It is clear that no \((r-1)\)-partite graph contains a copy of \(K_r\text{.}\) Assuming the number of edges is \(n\text{,}\) the number of edges in such a graph is maximized when every part is of size \(\lfloor n/(r-1)\rfloor\) or \(\lceil n/(r-1)\rceil\text{;}\) see Exercise 12 in Section 3.6. Such graphs are often referred to as Turán graphs.
Figure 3.2.2. The graph \(K_{2,2,2}\text{.}\)
Again, we will show that this construction is optimal. Note that the following theorem implies Mantel’s Theorem, but the proof that we will give, when specialized to the case \(r=3\text{,}\) will be different than the one given above. Thus, it gives an alternative proof.

Proof.

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.

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.

Remark 3.2.5.

Note that the proof of Turán’s Theorem given above also implies that the extremal graph for Turán’s Theorem is unique.
Here are a couple of YouTube videos related to Turán’s Theorem: