Teorema de Turán.

Paul Turán (foto abaixo) foi um matemático húngaro especialista em teoria dos números e combinatória. Neste post, veremos um dos resultados que iniciou a teoria extremal dos grafos: o Teorema de Turán.

Seja $G$ um grafo simples com $n$ vértices. Qual é o maior números de aresta que $G$ pode ter de modo que não tenhamos em $G$ uma $p$-clique?

Pensando por um momento, podemos elaborar um exemplo de um grafo $G = (V,E)$ com $n$ vértices sem uma $p$-clique e com bastantes arestas da seguinte maneira: particione $V$ em conjuntos $V_1,\ldots, V_{p-1}$ de modo que $| |V_i| - |V_j| | \leq 1$, para todo $i\neq j$, e conecte dois vértices se, e somente se, eles pertencerem a partições distintas. O grafo resultante é chamado de grafo de Turán e é denotado por $T^{p-1}(n)$ e seu número de arestas será denotado por $t_{p-1}(n)$.

Este grafo é um grafo $(p-1)$-multipartido. Entre todos os grafos $(p-1)$-multipartidos que não contém uma $p$-clique, aquele que definimos é o que tem o maior número de arestas, graças a condição $| |V_i| - |V_j| | \leq 1$, para todo $i\neq j$. De fato, suponhamos que $| |V_i| - |V_j| | \leq 2$, para algum par $i \neq j$. Podemos supor, sem perda de generalidade, que $|V_i| \geq |V_j| + 2$. Mudando um vértice de $V_i$ para $V_j$, temos que o novo grafo contém $(|V_i| - 1)(|V_j| + 1) - |V_1||V_j| = |V_i| - |V_j| - 1 \geq 1$ arestas a mais que o grafo anterior, gerando um grafo com um maior número de arestas. Portanto, é verdade que o grafo de Turán é o que contém o maior número de arestas entre todos os grafos $(p-1)$-multipartidos sem $p$-cliques.

Se $p-1$ divide $n$, temos que o grafo de Turán $T^{p-1}(n)$ é uma grafo $(p-1)$-multipartido regular, i.e., todas as $p-1$ partições contém o mesmo número de vértices: $n/(p-1)$. Assim, temos que
$$t_{p-1}(n) = \binom{p-1}{2}\left(\frac{n}{p-1}\right)^2 = \left( 1-\frac{1}{p-1} \right) \frac{n^2}{2}.$$
O que o Teorema de Turán afirma é que este número é um limitante superior para o número de aresta para qualquer grafo sobre $n$ vértices sem $p$-cliques.

Teorema (de Turán). Se um grafo $G=(V,E)$ em $n$ vértices não tem $p$ cliques, $p \geq 2$, então $$|E| \leq  \left( 1-\frac{1}{p-1} \right) \frac{n^2}{2}.$$

Este teorema é um dos belos exemplos em combinatória o qual se conhece várias provas e todas distintas entre si. O leitor que estiver interessado em conhecer algumas destas provas, poderá encontra cinco delas  no livro [1]. A prova que daremos aqui é retirada deste mesmo texto e é, dentre as cinco do livro, a mais bela, pois nos dá de cara que o grafo de Turán é o único exemplo de grafo com o número máximo de arestas.

Demonstração. Seja $G = (V,E)$ um grafo com $n$ vértices sem uma $p$-clique e com o número máximo de arestas.

Afirmação. G não contém três vértices $u$, $v$, $w$ tais que $vw\in E$, mas $uv\notin E$, $uw \notin E$.

Suponha que exista um trio de vértices $U,v,w$ com $vw\in E$, mas $uv\notin E$ e $uw\notin E$ (figura abaixo).

Consideramos dois casos:

Caso 1: $d(u) < d(v)$ ou $d(u) < d(w)$.
Suponha, sem perda de generalidade, que $d(u) < d(v)$ (o outro caso é análogo). Então, duplicamos $v$, i.e., criamos um novo vértice $v'$ que tem os mesmos vizinhos que $v$ (mas $vv'$ não é uma aresta. Veja a figua abaixo). Agora apagamos o vértice $u$. O novo grafo $G'$ assim obtido contém $n$ vértices e não possui uma $p$-clique. Além disso, temos que

$$|E(G')| = |E(G)| + d(v) - d(u) > |E(G)|,$$

o que contradiz o fato de $G$ ser o grafo sobre $n$ vértices sem $p$-clique com o maior número de arestas.

Caso 2: $d(u) \geq d(v)$ e $d(u) \geq d(w)$.
Duplicamos $u$ duas vezes, gerando os vértices $u'$ e $u''$ com os mesmos vizinhos que $u$ (figura abaixo). Apagamos os vértices $v$ e $w$. O novo grafo $G'$ ainda contém $n$ vértices e não possui uma $p$-clique. Quanto ao número de arestas de $G'$, temos que

$$|E(G')| = |E(G)| + 2d(u) - (d(v) + d(w) - 1) > |E(G)|.$$

Assim, temos mais uma vez uma contradição.

Agora defina relação $\sim$ sobre $V(G)$ da seguinte maneira:

$$u \sim v \Leftrightarrow uv \notin E(G).$$

Temos imediatamente que $\sim$ é reflexiva e simétrica. A afirmação que acabamos de provar nos permite concluir que $\sim$ é transitiva: se $v \sim u$ e $u \sim w$, então $v \sim w$, do contrário teríamos $vw\in E$, mas $uv\notin E$, $uw \notin E$, o que não pode ocorrer, como provado na afirmação.

Mas uma vez $\sim$ define uma relação de equivalência sobre $V(G)$, os vértices de $G$ são particionados em classes de equivalência de tal maneira que $G$ é um grafo multipartido. Ora, dentre todos os grafos multipartidos sobre $n$ vértices, aquele que não contém uma $p$-clique e contém o maior número de arestas é o $T^{p-1}(n)$. Isto conclui a prova do teorema.

Referências.

[1] Martin Aigner, Günter M. Ziegler; As porvas estão n'O LIVRO. Editora Edgard Blücher, 2002.