Mostre que toda árvore com, pelo menos, uma aresta deve ter, pelo menos, dois vértices pendentes.

Passo 1

O enunciado pede para mostrar que, em qualquer árvore (isto é, grafo conexo e sem ciclos) que tenha pelo menos uma aresta, há pelo menos dois vértices de grau 1 — chamados de vértices pendentes. Para isso, vamos usar a ideia de escolher um caminho simples de comprimento máximo na árvore e analisar o grau de seus extremos.

Passo 2

Seja T a árvore em questão e suponha que ela tenha pelo menos uma aresta. Considere um caminho simples de comprimento máximo em T, digamos
P = (x_0, x_1, x_2,\dots, x_k)
com k\ge1. Como P é de comprimento máximo, não existe caminho em T com mais de k arestas.
Agora, olhemos para o extremo x_0. Se \deg(x_0)\ge2, existiria uma aresta \{x_0,y\} com y\neq x_1. Então poderíamos extender P para
(y,x_0,x_1,\dots,x_k),
obtendo um caminho de comprimento k+1, o que contradiz a maximalidade de P. Logo não há outra aresta em x_0 além de \{x_0,x_1\}, o que implica
\deg(x_0)=1.
O mesmo raciocínio vale para o outro extremo x_k, mostrando que
\deg(x_k)=1.

Passo 3

Como k\ge1, os vértices x_0 e x_k são distintos. Portanto, T tem pelo menos dois vértices com grau 1, ou seja, dois vértices pendentes.

Resposta

Em toda árvore com pelo menos uma aresta existem, no mínimo, dois vértices pendentes.

Exercícios de Livros Relacionados