OliForum Matematico

Dato un albero (finito) $\mathcal{T}$, dimostrare che se non ci sono vertici con valenza $2$ in $\mathcal{T}$, allora il numero di foglie è maggiore del numero degli altri vertici.

Nota. Vabbè, tanto lo sapete. Comunque, un albero è un grafo connesso senza cicli e una foglia è un vertice di un albero con valenza $1$.

Allora, è abbastanza noto che un albero di $V$ vertici ha esattamente $V-1$ lati; ma con un double counting abbastanza standard sulla valenza totale del grafo (chiamato $f$ il numero di foglie) si ha
$$2(V-1)=\sum_{v} \deg(v)\Rightarrow 2(V-1)=f+\sum_{v\ne f} \deg(v)$$
Supponendo che non ci siano vertici di valenza $2$, al minimo ogni vertice che non è una foglia (sono $V-f$) avrà valenza $3$, da cui
$$2(V-1)=f+\sum_{v\ne f} \deg(v)\geq f+\sum_{v\ne f} 3= f+3(V-f)$$
Dunque, risolvendo la disequazione si ottiene
$$2f\geq V+2\Rightarrow f\geq \frac{V}{2}+1$$
Quindi le foglie sono sicuramente più della metà dei vertici totali e abbiamo dimostrato la tesi.