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
a árvore em questão e suponha que ela tenha pelo menos uma aresta. Considere um caminho simples de comprimento máximo em
, digamos
com
. Como
é de comprimento máximo, não existe caminho em
com mais de
arestas.
Agora, olhemos para o extremo
. Se
, existiria uma aresta
com
. Então poderíamos extender
para
obtendo um caminho de comprimento
, o que contradiz a maximalidade de
. Logo não há outra aresta em
além de
, o que implica
O mesmo raciocínio vale para o outro extremo
, mostrando que
Passo 3
Como
, os vértices
e
são distintos. Portanto,
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.