Teoría de Grafos - Hojas vs. Nº de vértices grado 3+

Question

Estoy estudiando el Problema 35, Capítulo 10 de A Walk Through Combinatorics de Miklos Bona, que dice...

Demostrar que un árbol siempre tiene más hojas que vértices de grado al menos 3.

Siento que debería haber un argumento inductivo con respecto a n, la cantidad de vértices, pero no sé cómo contar los vértices de grado 3+. Alguien tiene una idea de cómo empezar esto?

Answer 1

Deja que el árbol $T$ tienen $A_1$ vértices de grado $1$ , $A_2$ vértices de grado $2$ etc.

Entonces $$\sum_v \operatorname{deg}(v) = \sum_{i=1}^n i A_i = 2(n-1).$$ Pero sabemos que $\sum_{i=1}^n A_i = n$ Así que $$\sum_{i=1}^n (i-2)A_i = -A_1 + A_3 + 2A_4 + 3A_5 + \dots = -2.$$ ¿Puedes terminarlo desde ahí?