Mostre que uma árvore com
vértices que tem
vértices pendentes deve ser isomorfa a
.
Passo 1
O enunciado diz que temos uma árvore com
vértices e exatamente
vértices pendentes (folhas). O objetivo é mostrar que essa árvore é isomorfa ao grafo estrela
. Vamos usar o fato de que, em qualquer grafo, a soma dos graus dos vértices vale o dobro do número de arestas (fórmula do aperto de mãos) e a definição de árvore (grafo conectado e acíclico com
arestas).
Passo 2
Seja
a nossa árvore, com conjunto de vértices
. Denotemos por
o conjunto das folhas de
, e por
o único vértice que não é folha. Como há
vértices no total e
folhas, segue que
Passo 3
Pela fórmula do aperto de mãos, temos
Como
é árvore com
vértices,
. Logo
Passo 4
Cada folha tem grau 1, e há
folhas. Então a soma dos graus dessas folhas é
Como a soma total dos graus é
, o grau de
deve ser
Passo 5
O vértice
tem grau
, ou seja, está ligado a todos os outros
vértices. E como os demais vértices são exatamente folhas, cada aresta em
conecta
a uma folha. Isso mostra que
é precisamente a estrela
.
Resposta
A árvore é isomorfa a
.