Seja
um grafos simples não-direcionado com
vértices. Prove que, se
não possui um grafo
como subgrafo, então o número de arestas de
é no máximo
.
Dica: em
, se
e
são dois vértices vizinhos,
, pois, se
, existiria um vértice
vizinho a ambos, formando assim um subgrafo
.
Dica: em
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
, temos
. 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
(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
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
.