Clique-Free Extremal Numbers from Turán's Theorem

From a Forbidden Clique to an Edge Count

Extremal graph questions ask how many edges a graph can have while avoiding a specified subgraph. For a forbidden clique, Turán’s theorem gives an exact answer: the extremal graph is complete multipartite, with its parts as equal in size as possible. The calculation has two decisions. First, translate the forbidden clique into the correct number of parts; then distribute the vertices among those parts and count the edges between them.

All graphs in this tutorial are finite, simple, and undirected. A subgraph is not required to be induced. Thus a graph is \(K_{r+1}\)-free if it has no set of \(r+1\) vertices that are pairwise adjacent. For a fixed forbidden graph \(F\), \(\operatorname{ex}(n,F)\) denotes the largest number of edges in an \(n\)-vertex graph containing no subgraph isomorphic to \(F\).

The number of parts is determined by the forbidden clique: to avoid \(K_{r+1}\), use \(r\) parts, not \(r+1\). A clique in a complete \(r\)-partite graph can have at most one vertex from each part, so it has at most \(r\) vertices. Turán’s theorem says that among all \(K_{r+1}\)-free graphs on \(n\) vertices, \(T_r(n)\) has the maximum number of edges. The theorem and its proof by symmetrization were established in the earlier material on Turán’s theorem; here we use it to obtain explicit extremal numbers.

Counting Edges from the Part Sizes

Let a complete \(r\)-partite graph have parts of sizes \(a_1,\ldots,a_r\), where each \(a_i\) is a nonnegative integer and \(\sum_{i=1}^{r}a_i=n\). Each edge joins vertices in two different parts. This gives a direct count, and a second count follows by starting with all vertex pairs and removing the pairs that lie within a part.

Proof. For each pair of distinct parts \(i,j\), there are \(a_i a_j\) vertex pairs with one endpoint in each part, and all of them are edges. Summing over the pairs of parts gives \(|E|=\sum_{i<j}a_i a_j\). Also, \[ \left(\sum_{i=1}^{r}a_i\right)^2 =\sum_{i=1}^{r}a_i^2+2\sum_{i<j}a_i a_j. \] Since \(\sum_i a_i=n\), rearranging gives the stated formula. The argument also covers empty parts, whose contributions are zero. \(\square\)

To calculate the sizes in \(T_r(n)\), divide \(n\) by \(r\). Write \[ n=qr+s,\qquad q=\left\lfloor\frac nr\right\rfloor,\qquad 0\le s<r. \] The balanced parts consist of \(s\) parts of size \(q+1\) and \(r-s\) parts of size \(q\). Indeed, their total size is \(s(q+1)+(r-s)q=qr+s=n\), and their sizes differ by at most one.

Proof. By Turán’s theorem, the maximum number of edges in an \(n\)-vertex \(K_{r+1}\)-free graph is the number of edges in \(T_r(n)\). The part sizes of \(T_r(n)\) are \(s\) copies of \(q+1\) and \(r-s\) copies of \(q\), so the sum of their squares is \(s(q+1)^2+(r-s)q^2\). Substituting these sizes into the lemma gives the displayed edge count, and therefore the stated value of \(\operatorname{ex}(n,K_{r+1})\). If \(r>n\), then \(q=0\) and \(s=n\); the formula gives \(\binom n2\), as \(T_r(n)\) is the complete graph on \(n\) vertices. If \(r=1\), it gives zero, as a \(K_2\)-free graph has no edges. \(\square\)

Worked Applications

Reading the Formula and Avoiding a Common Error

The formula is a practical calculation rule: identify \(r\) as one less than the forbidden clique size, divide \(n\) by \(r\), and use the quotient and remainder to form the balanced part sizes. The direct sum \(\sum_{i<j}a_i a_j\) is often the quickest way to count edges when there are only a few distinct part sizes. The square-sum expression is convenient for checking the count or applying the result to larger values.

Common mistake: using the forbidden clique size as the number of parts. Forbidding \(K_4\) means \(K_{3+1}\)-free, so the Turán graph has three parts. For example, on 12 vertices the relevant graph is \(T_3(12)\), with three parts of size \(4\), not four parts. Its edge count is \(\binom32(4\cdot4)=3\cdot16=48\). Equivalently, the square-sum calculation is \[ \frac12\left(12^2-3\cdot4^2\right) =\frac12(144-48)=48. \] Using four parts would instead construct a graph associated with forbidding \(K_5\), which answers a different extremal question.

A second useful check is to remember what is being counted: \(T_r(n)\) has edges only between different parts. Summing the sizes of the parts does not count edges, and counting within-part pairs gives nonedges, not edges. To check any calculation, either add all cross-part products or subtract all within-part pairs from \(\binom n2\).