Sejam $H$ um grafo com conjunto de arestas não vazio e $n\ge\vert H\vert$.

<WRAP round help 70%>
Qual é a maior quantidade de arestas que um grafo de $n$ vértices pode ter sem conter um subgrafo isomorfo a $H$?
</WRAP>

<WRAP round info 70%>
Um grafo $G$ de $n$ vértices tal que $H\not\subset G$ e com a maior quantidade possível de arestas é chamado **extremal** para $n$ e $H$. Nesse caso, sua quantidade de arestas é denotada por $ex(n,H)$. 
</WRAP>

Claro que qualquer grafo $G$ extremal para $n$ e $H$ é [[grafos:maximal|maximal em arestas]] com $H\not\subset G$. No entanto, maximalidade em arestas //não// implica em extremalidade.
Por exemplo, ambos os grafos abaixo são maximais em arestas sem $K^3$ como subgrafo (isto é, adicional uma aresta em qualquer um deles faria conter um $K^3$); porém, como o da direita possui mais arestas, o da esquerda não é extremal.

{{ :grafos:maximal_5_k3.png?400 |}}
No que segue, vamos considerar o caso $H=$ [[grafos:defcompleto|$K^r$]] (com $r>1$).

É fácil ver que todo grafo [[grafos:defbipartite|$(r-1)$-partido]] [[grafos:defcompleto|completo]] é maximal em arestas sem $K^r$ como subgrafo.
Além disso, o grafo $(r-1)$-partido completo com $n$ vértices e maior quantidade de arestas é aquele cujos conjuntos da partição diferem de no máximo $1$ em tamanho. Um tal grafo é dito **grafo de Turán**; o denotamos por $T^{r-1}(n)$ e sua quantidade de arestas por $t_{r-1}(n)$.

<WRAP round box 70%>
=== Teorema de Turán ===
Todo grafo extremal para $n$ e $K^r$ é isomorfo a $T^{r-1}(n)$.
</WRAP>

Seja $G$ um grafo extremal para $n$ e $K^r$.

__Prova 1__ (por indução em $n$):

Para $n\le r-1$, temos $G=K^n=T^{r-1}(n)$.

Passo indutivo: Seja $N\ge r$. Como $G$ é maximal em arestas sem $K^r$ como subgrafo, existe $K\simeq K^{r-1}\subset G$ (pois, caso contrário, aresta alguma adicionada a $G$ produziria um $K^r$ como subgrafo).

Por hipótese, $G-K$ tem, no máximo, $t_{r-1}(n-(r-1))$ arestas e cada vértice de $K$ tem, no máximo, $(r-1)-1$ vizinhos em $K$. Logo
$$\Vert G\Vert\le t_{r-1}(n-(r-1))+(n-(r-1))((r-1)-1)+\binom{r-1}{2}=t_{r-1}(n).$$

Como $G$ é extremal para $K^n$ e $T^{r-1}(n)\not\supset K^n$, vale a igualdade acima. Então todo vértice de $G-K$ tem //exatamente// $r-2$ vizinhos em $K$, assim como os vértices $x_1,\cdots,x_{r-1}$ de $K$.

Seja $V_i:=\{v \in V(G):vx_i \not\in E(G)\}$ o conjunto dos vértices de $G$ cujos $r-2$ vizinhos em $K$ são todos os vértices diferentes de $x_i$.
Como $K^n\not\subset G$, os conjuntos $V_i$ são [[grafos:conjuntoindependente|independentes]] e particionam $V(G)$. Logo $G$ é $(r-1)$-partido.

Como $T^{r-1}(n)$ é o único grafo $(r-1)$-partido de $n$ vértices e maior quantidade de arestas sem $K^r$ como subgrafo, segue $G=T^{r-1}(n)$ pela extremalidade de $G$.

__Prova 2__:

Note que um grafo $(V, E)$ é completo multipartido se, e somente se, a relação $\sim$ sobre $V$ dada por "$a\sim b$ se $ab\not\in E$" é transitiva. Assim, se $G$ não é um grafo multipartido completo, existem $a, b, c\in V$ com $ab, bc\not\in E$ e $ac\in E$.

Se $d(a) > d(b)$, então eliminando $b$ e duplicando $a$ obtemos um novo grafo sem $K^r$ como subgrafo e com mais arestas que $G$, contradizendo sua extremalidade. Então $d(a)\le d(b)$ e, de modo similar, $d(c)\le d(b)$. Mas, então, eliminando ambos $a$ e $b$ e triplicando $b$ obtemos um novo grafo sem $K^r$ como subgrafo com mais arestas que $G$, novamente contradizendo a sua extremalidade.

Dessa forma, segue que $G$ é completo multipartido, portanto, deve ser isomorfo a $T^{r-1}(n)$.