Turán's theorem
= Turán's theorem
{c}
{title2=$\operatorname{ex}(n,K_{r+1})=t_r(n)$}
{wiki}
= Turan theorem
{c}
{synonym}
How many <edges> can we retain while excluding a prescribed <clique>? For <integers> $r\geq1$ and $n\geq0$, every <simple graph> on $n$ <vertices> containing no <complete subgraph> $K_{r+1}$ satisfies
$$
e(G)\leq t_r(n):=e(T_r(n)).
$$
Equality holds exactly for the <Turán graph> $T_r(n)$, up to <graph isomorphism>. Thus the <extremal number> is $\operatorname{ex}(n,K_{r+1})=t_r(n)$.<Graph Theory by Reinhard Diestel>[third electronic edition (2005), §7.1, printed p. 165, Theorem 7.1.1; replace the source's forbidden-clique parameter r by r+1]{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)$.<Graph Theory by Reinhard Diestel>[third electronic edition (2005), §7.1, printed pp. 166–167, vertex duplication and second proof of Theorem 7.1.1]{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\geq n$, the <Turán graph> is $K_n$, and the bound is the total $\binom n2$ possible <edges>.