Mostre que uma árvore com n vértices que tem n-1 vértices pendentes deve ser isomorfa a K_{1, n-1}.

Passo 1

O enunciado diz que temos uma árvore com n vértices e exatamente n-1 vértices pendentes (folhas). O objetivo é mostrar que essa árvore é isomorfa ao grafo estrela K_{1,n-1}. 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 n-1 arestas).

Passo 2

Seja T a nossa árvore, com conjunto de vértices V(T). Denotemos por L o conjunto das folhas de T, e por u o único vértice que não é folha. Como há n vértices no total e n-1 folhas, segue que
|L| = n-1 \quad\text{e}\quad V(T)\setminus L = \{u\}.

Passo 3

Pela fórmula do aperto de mãos, temos
\sum_{v\in V(T)} \deg(v) \;=\; 2\,|E(T)|.
Como T é árvore com n vértices, |E(T)|=n-1. Logo
\sum_{v\in V(T)} \deg(v) = 2(n-1).

Passo 4

Cada folha tem grau 1, e há n-1 folhas. Então a soma dos graus dessas folhas é
\sum_{v\in L}\deg(v) = (n-1)\cdot 1 = n-1.
Como a soma total dos graus é 2(n-1), o grau de u deve ser
\deg(u) = 2(n-1) - (n-1) = n-1.

Passo 5

O vértice u tem grau n-1, ou seja, está ligado a todos os outros n-1 vértices. E como os demais vértices são exatamente folhas, cada aresta em T conecta u a uma folha. Isso mostra que T é precisamente a estrela K_{1,n-1}.

Resposta

A árvore é isomorfa a K_{1,n-1}.

Exercícios de Livros Relacionados