Se G é uma árvore com 8 vértices onde 3 dos seus vértices têm grau 3, quantas folhas G possui? Justifique a sua resposta.

Passo 1

Beleza, vamos lá! O problema fala sobre árvores na teoria dos grafos. Uma árvore é um tipo especial de grafo que não tem ciclos e está todo conectado. Aqui, temos uma árvore com 8 vértices e 3 desses vértices têm grau 3. Nosso objetivo é descobrir quantas folhas (vértices com grau 1) essa árvore possui. Para resolver isso, vamos precisar usar algumas propriedades básicas das árvores e a soma dos graus dos vértices.

Passo 2

Primeiro, vamos lembrar que em qualquer grafo, a soma dos graus de todos os vértices é igual ao dobro do número de arestas. Isso é conhecido como o Teorema do Aperto de Mãos. Em uma árvore com n vértices, sempre tem n - 1 arestas. No nosso caso, com 8 vértices:
Número de arestas = 8 - 1 = 7 ú
Portanto, a soma dos graus de todos os vértices será:
Soma dos graus = 2 times 7 = 14

Passo 3

Agora, sabemos que 3 vértices têm grau 3 cada. Vamos calcular a contribuição desses vértices para a soma total dos graus:
3 vértices times 3 = 9 é
Isso significa que os 5 vértices restantes (já que temos 8 no total) devem somar os graus restantes:
14 (soma total) - 9 = 5

Passo 4

Os vértices que não são de grau 3 podem ser folhas (grau 1) ou ter outros graus. Mas, em uma árvore, a única possibilidade para os vértices restantes que somam 5 é cada um ter grau 1, já que se algum tivesse grau maior, a soma total excederia 5. Assim, cada um dos 5 vértices restantes é uma folha.

Resposta

A árvore possui 5 folhas.

Exercícios relacionados