Seja G um grafos simples não-direcionado com n vértices. Prove que, se G não possui um grafo K3 como subgrafo, então o número de arestas de G é no máximo n^2 / 4.
Dica: em G, se x e y são dois vértices vizinhos, d(x)+d(y) <= n-1, pois, se d(x)+d(y) >= n, existiria um vértice z neq x, y vizinho a ambos, formando assim um subgrafo K3 em G.

Passo 1

Vamos entender o que o exercício está pedindo. Temos um grafo simples não-direcionado com vértices. A questão quer que a gente prove que, se esse grafo não tem um triângulo (um subgrafo ), então o número máximo de arestas que pode ter é . Para resolver isso, vamos precisar usar conceitos básicos de grafos, como grau dos vértices e a ideia de subgrafos.

Passo 2

Primeiro, vamos lembrar que o grau de um vértice é o número de arestas que incidem nele. A dica nos diz que para quaisquer dois vértices adjacentes e , a soma de seus graus é no máximo . Isso ocorre porque se essa soma fosse , haveria outro vértice conectado a ambos e , formando um triângulo , o que contraria a condição do problema.

Passo 3

Vamos somar as somas dos graus de todos os pares de vértices adjacentes no grafo. Como cada aresta conecta dois vértices, ao somarmos para todas as arestas , estamos contando cada grau de vértice uma vez para cada aresta que ele possui. Portanto, essa soma será igual a , onde é o número de arestas no grafo.

Passo 4

Da dica, sabemos que para cada aresta 2|E| <= |E| times (n - 1) , temos |E| <= n - 12 |E| . Portanto, somando sobre todas as arestas, temos:
Dividindo ambos os lados por :
No entanto, isso não nos dá diretamente a informação desejada. Para avançar, podemos considerar a média dos graus dos vértices.

Passo 5

A soma dos graus de todos os vértices é igual a d = 2|E|n (pela relação mão-direita). Vamos chamar a média dos graus, então:
Queremos encontrar um limite para , então queremos expressar isso em termos de .

Passo 6

Usando a desigualdade de média, e sabendo que para qualquer par de vértices adjacentes, podemos aplicar o Teorema de Turán, que nos diz que o número máximo de arestas em um grafo com vértices sem como subgrafo é dado pela Turán graph . No nosso caso, como estamos evitando , temos .

Passo 7

O Teorema de Turán para |E| <= n^24 nos diz que o número máximo de arestas é alcançado por um grafo bipartido completo equilibrado, onde os vértices são divididos em dois grupos de tamanho aproximadamente . O número de arestas nesse caso é:

Resposta

Portanto, se não contém um triângulo como subgrafo, o número máximo de arestas de é no máximo .

Exercícios relacionados