Seja T uma árvore com n ≥ 2 vértices. Prove as seguintes afirmações: 1. (1,0 pts) T tem pelo menos 2 (duas) folhas 2. (2,0 pts) Para k ∈ N, se...

1. Para provar que T tem pelo menos 2 folhas, podemos utilizar o seguinte raciocínio: se T tem apenas um vértice, então ele não tem folhas. Se T tem dois vértices, então ele tem uma aresta que os conecta, e essa aresta é uma folha. Se T tem mais de dois vértices, podemos remover uma folha de T (se existir) e obter uma nova árvore T' com n-1 vértices. Como T' tem menos vértices que T, podemos aplicar o mesmo raciocínio para T' e concluir que T' tem pelo menos uma folha. Como T' é obtido a partir de T por remoção de uma folha, concluímos que T também tem pelo menos uma folha. Portanto, T tem pelo menos 2 folhas. 2. Para provar que se ∆(T) ≥ k, então existem pelo menos k folhas, podemos utilizar o seguinte raciocínio: se T tem apenas um vértice, então ele não tem folhas e ∆(T) = 0. Se T tem mais de um vértice, podemos escolher um vértice v de T com grau máximo ∆(T). Como v tem grau máximo, todos os seus vizinhos têm grau menor ou igual a ∆(T). Podemos remover v e seus vizinhos de T e obter uma nova árvore T' com n' vértices e ∆(T') < ∆(T). Como ∆(T) ≥ k, temos ∆(T') ≥ k-1. Podemos aplicar o mesmo raciocínio para T' e concluir que T' tem pelo menos k-1 folhas. Como removemos v e seus vizinhos de T, temos que T tem pelo menos 1 folha. Portanto, T tem pelo menos k folhas.