13 views

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

retagged | 13 views

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.