Se
é uma árvore com 8 vértices onde 3 dos seus vértices têm grau 3, quantas folhas
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:
Portanto, a soma dos graus de todos os vértices será:
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:
Isso significa que os 5 vértices restantes (já que temos 8 no total) devem somar os graus restantes:
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.