Prove that in a tree with maximum degree , there are at least leaves

Question

Prove that in a tree with maximum degree $k$, there are at least $k$ leaves.

Answer 1

Recall: We know that sum of all degree of vertices in a simple graph $G$ is twice its number of edge. Let $E(G)$ be the edge set of $G$ and $V(G)$ be the vertex set of $G$. Then
$$\sum_{v\in G} d(v) =2|E(G)|$$

---

Let $T$ be a tree on $n$ vertices with a maximum degree $k$. Then by the above result we know that 

$$\sum_{v\in T} d(v)=2|E(T)|= 2(n-1)$$

Let there are $\ell$ many leaves in the tree $T$. We have to prove that $k\leq \ell$.

---

Note that there are $n-\ell$ vertices in $T$ with degree at least $2$. Amon all those $n-\ell$ vertices there will be at least one vertex with degree exactly $k$. That means, there are $n-\ell-1$ vertices with degree at least two and one vertex with degree exactly $k$. It follows that 

$$\sum_{v\in T}d(v) \geq \ell + (n-\ell-1)\cdot 2+k = 2(n-1)+(k-\ell).$$

---

Therefore it follows that 

$$2(n-1)=\sum_{v\in T}d(v)  \geq  2(n-1)+(k-\ell) \implies k-\ell \leq 0$$

This completes the proof.