Turán's theorem and extremal density

Fix integers $n\ge r\ge2$. Divide the vertices into $r$ independent parts and join every pair in different parts. This complete multipartite graph contains no clique on $r+1$ vertices, because a clique can use at most one vertex from each independent part. Its edge count is half the difference between the square of the total size and the sum of squared part sizes. The division by two removes the two orientations of each edge.

For a fixed total number of vertices, balancing the parts maximizes the edge count. If one part exceeds another by at least two, moving a vertex from the larger part to the smaller decreases the sum of squared sizes and therefore increases the edges. Repeat until all sizes differ by at most one. The resulting graph is the Turán graph $T_r(n)$; the label r counts parts, while the forbidden clique has r plus one vertices.

Turán's theorem says every graph on n vertices with no $K_{r+1}$ has at most as many edges as $T_r(n)$. Equality occurs exactly for a graph isomorphic to that balanced complete r-partite graph. The statement supplies both a universal upper bound and the unique extremal structure, up to vertex relabeling. The theorem's general proof is not supplied here; symmetrization arguments transform an extremal graph into a multipartite one without losing edges or introducing the forbidden clique.

The triangle case has a short direct bound. If vertices u and v are adjacent in a triangle-free graph, their neighborhoods are disjoint, so their degrees sum to at most n. Summing over edges gives a bound on the sum of squared degrees. Cauchy–Schwarz supplies the opposite bound in terms of the total degree, and combining them yields at most n squared divided by four edges. Integer rounding gives Mantel's exact threshold. This proof illustrates how a local prohibition creates a global inequality.

We use edge density $e(G)/\binom n2$ when n is at least two. For fixed r, the Turán density approaches $1-1/r$ as n grows. The exact finite fraction can be larger than this limit because the denominator omits loops while the leading quadratic approximation uses n squared. For example, a balanced complete bipartite graph on four vertices has density four sixths, despite the asymptotic triangle-free threshold being one half. There is no contradiction between these two statements.

A sharp extremal theorem does not automatically classify every graph just below the threshold. Stability is a separate assertion that nearly extremal forbidden-pattern-free graphs are close to the extremal construction in a specified edit distance. Likewise, exceeding the threshold by one forces a clique, but it does not by this theorem alone give a sharp count of all cliques. The next lesson replaces an existence conclusion with a quantitative abundance conclusion and makes the limiting quantifiers explicit.