Turán's theorem ($\mathrm{ex}(n,K_{r+1})=t_r(n)$)

How many edges can we retain while excluding a prescribed clique? For integers $r\ge 1$ and $n\ge 0$, every simple graph on $n$ vertices containing no complete subgraph $K_{r+1}$ satisfiesEquality holds exactly for the Turán graph $T_r(n)$, up to graph isomorphism. Thus the extremal number is $\mathrm{ex}(n,K_{r+1})=t_r(n)$.^[ref]

For example, $T_3(8)$ has independent sets of sizes $3,3,2$ and $21$ edges, as counted in Turán graph. It contains triangles in a graph, but no four-vertex clique. Consequently any simple graph on eight vertices with $22$ edges contains $K_4$, while $21$ edges alone do not force one. Excluding larger cliques permits denser graphs; Mantel theorem is precisely the first nontrivial case.

A short proof outline uses Zykov symmetrization. If an extremizer is not a complete multipartite graph, it has vertices $x,y,z$ with $xy,xz$ absent and $yz$ present. If either $y$ or $z$ has larger vertex degree than $x$, clone that vertex in place of $x$. Otherwise replace both $y,z$ by nonadjacent clones of $x$, gaining $2d(x)-d(y)-d(z)+1>0$ edges. Both contradict extremality; balancing the resulting at most $r$ parts gives $T_r(n)$.^[ref]

The vertex cloning in a graph step preserves clique exclusion because any clique using a clone can substitute its original vertex; nonadjacent clones cannot occur together in a clique. At most $r$ parts can be nonempty, since selecting one vertex from each gives a clique. If fewer than $r$ parts are nonempty and one has at least two vertices, splitting it creates more edges, so it cannot be extremal. For $r=1$ the bound is zero. For $r\ge n$, the Turán graph is $K_n$, and the bound is the total $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ possible edges.

A clique-free graph near the Turan theorem edge bound is close to a complete multipartite graph. Choose a maximum-degree vertex, split its neighbourhood from the remaining vertices, and apply induction inside the neighbourhood. The degree bound implies that missing cross edges are at least twice the number of edges inside the remaining class. This inequality controls all three types of edits and gives the constant three.

Fix an odd cycle length. If the graph has edge density at least $1/2-ϵ$ and sufficiently few copies of that cycle, odd-cycle copies from positive triangle density forces few triangles in a graph. The triangle removal lemma deletes at most $ϵ\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges, after which the clique-free edit bound applies with two parts. Absorbing its linear rounding error into the density margin gives the displayed bound for large order.

The Turán graph $T_r(n)$ is a complete multipartite graph with $r$ independent sets of sizes differing by at most one, with every cross edge present. Empty parts are allowed when $r>n$.^[ref]

In this example, the independent sets are $A=\{a_1,a_2,a_3\}$, $B=\{b_1,b_2,b_3\}$ and $C=\{c_1,c_2\}$. Count the edges between each pair of parts:Any four vertices put at least two in the same independent set, by the pigeonhole principle, so they cannot form $K_4$. Conversely, every choice of one vertex from each part is a triangle in a graph, giving $3\cdot 3\cdot 2=18$ triangles in a graph. Clique exclusion here does not mean triangle-free.

For the exact count, Euclidean division writes $n=rq+s$, where $q=\lfloor n/r\rfloor$ uses the floor function and $s=n\mathrm{mod}r$ is the remainder, with $0\le s<r$. There are $s$ parts of size $q+1$ and $r-s$ of size $q$. For any part sizes $a_1,\dots ,a_r$ summing to $n$, count cross edges by expanding the square:ThereforeFor $n=8,r=3$, we have $q=2,s=2$, giving $(64-2\cdot 9-1\cdot 4)/2=21$. The Quadratic Turan edge bound gives $64/3$ instead: the exact correction subtracts $1/3$.

Balancing is an integer optimization with a simple reason. If two part sizes satisfy $a\ge b+2$, moving one vertex from the larger part to the smaller decreases their contribution to the sum of squares byso it increases the edge count by $a-b-1$. For eight vertices, parts $4,2,2$ give $20$ edges; moving one vertex produces $3,3,2$ and $21$ edges. The most symmetric permitted sizes pack the most cross edges, which explains the sharp construction in Turán's theorem.

For $n\ge 3$, put $e_i=e(T_i(n))$, $t_3=k_3(T_3(n))$, and $c_n=(e_3-e_2)/t_3$. Every graph on $n$ vertices satisfiesThus an edge count $e_2+\theta (e_3-e_2)$ forces at least $\theta t_3$ triangles in a graph. This is an exact finite bound, with the rounding in the Turán graph retained. To prove it, use edge-triangle symmetrization. The inequality $c_n\ge 2/n$ allows merging the two smallest classes when there are at least four classes. With three classes, fixing the middle class makes the objective affine in the product of the other two sizes; either merge them or balance them. Only $T_2(n)$ and $T_3(n)$ need remain.

Zykov symmetrization replaces one of two nonadjacent vertices by a clone of the other. Cloning the vertex of larger degree does not decrease the edge count and does not create a larger clique. Iteration reduces the extremal problem for clique-free graphs to complete multipartite graphs.

For each real $c$, some maximizer of $e(G)-c{k}_3(G)$ among graphs on $n$ vertices is complete multipartite graph. Among maximizers maximize ${\sum }_{v}d(v{)}^2$. Cloning either of two nonadjacent vertices preserves the objective, since maximality forces their local contributions $d(v)-ce(G[N(v)])$ to agree. If their vertex neighbourhoods differ, the sum of the two changes in the squared-degree of a vertex objective is twice the size of their symmetric difference, a contradiction. Nonadjacency therefore partitions the vertices into classes with identical vertex neighbourhoods.

Every $n$-vertex graph containing no $K_{r+1}$ satisfies

A graph-theoretic rhombus is two triangles sharing an edge. Every rhombus-free graph on $n\ge 4$ vertices has at mostedges. If the graph is triangle-free this is Turán's theorem. Otherwise remove a triangle: every remaining vertex has at most one neighbor in it, and induction bounds the edge count by
$\lfloor (n-3{)}^2/4\rfloor +n\le \lfloor n^2/4\rfloor$.

The triangular prism has six vertices and nine edges. Each edge lies in at most one triangle, so it has no rhombus; its two triangles show that it is not $K_{3,3}=T_2(6)$.

This is the prism graph built from two triangles.