Seja G um grafo tal que |A(G)|>|V(G)|. Mostre que g(v) >= 3 para algum vértice v.

Passo 1

Ok, vamos resumir o que o exercício está pedindo. Temos um grafo onde o número de arcos (ou seja, arestas) é maior que o número de vértices, isto é, . A tarefa é mostrar que pelo menos um vértice nesse grafo tem grau (número de arestas que incidem sobre ele) maior ou igual a 3, ou seja, .
Vamos precisar usar conceitos básicos de teoria dos grafos, especialmente a relação entre o número de vértices, arestas e os graus dos vértices. Além disso, vamos aplicar a fórmula da mão dos dedos, que relaciona esses elementos.

Passo 2

Primeiro, vamos lembrar da fórmula da mão dos dedos. Essa fórmula nos diz que a soma dos graus de todos os vértices de um grafo é igual a duas vezes o número de arestas. Em termos matemáticos:
sumv in V(G) g(v) = 2|A(G)|
Isso acontece porque cada aresta contribui com 2 para a soma dos graus (uma para cada vértice que a aresta conecta).

Passo 3

Sabemos que sumv in V(G) g(v) = 2|A(G)| > 2|V(G)| . Vamos usar essa informação na fórmula da mão dos dedos:
Portanto, a soma dos graus dos vértices é maior que o dobro do número de vértices.

Passo 4

Vamos imaginar que todos os vértices tivessem grau menor que 3, ou seja, sumv in V(G) g(v) < 3|V(G)| para todo 2|V(G)| < sum g(v) < 3|V(G)| . Nesse caso, a soma dos graus seria:
Mas sabemos que . Então ter todos os graus menores que 3 implicaria que:
Isso parece possível, mas vamos ver melhor.

Passo 5

Se assumirmos que todos os vértices têm sumv in V(G) g(v) <= 2|V(G)| , então a soma dos graus seria no máximo:
Mas também sabemos que , o que cria uma contradição. Isso significa que nossa suposição de que todos os vértices têm grau menor que 3 está errada.

Passo 6

Portanto, não é possível que todos os vértices tenham grau menor que 3. Isso implica que pelo menos um vértice deve ter .

Resposta

Assim, demonstramos que se , então existe pelo menos um vértice no grafo com grau .

Exercícios relacionados