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

Claro que qualquer grafo $G$ extremal para $n$ e $H$ é 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.

No que segue, vamos considerar o caso $H=$ $K^r$ (com $r>1$).

É fácil ver que todo grafo $(r-1)$-partido 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)$.

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 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)$.