Seja
um grafo tal que
. Mostre que
para algum vértice
.
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:
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
. 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,
para todo
. 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
, 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
.