Qual é a soma dos graus dos vértices de uma árvore \operatorname{com} n vértices?

Passo 1

O enunciado apresenta uma árvore com n vértices e pede a soma dos graus de todos os vértices. Esse problema pertence à teoria dos grafos, e vamos usar o conceito de grau de vértice junto com o lema das mãos (handshaking lemma).

Passo 2

Pelo lema das mãos, em qualquer grafo vale
\sum_{v\in V} \deg(v) \;=\; 2\,|E|.
Como uma árvore com n vértices tem exatamente |E|=n-1 arestas, basta substituir:
\sum_{v\in V} \deg(v) \;=\; 2\,(n-1) \;=\; 2n - 2.

Resposta

2n - 2

Exercícios de Livros Relacionados