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

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

So I said:

$2|E| = \sum_{v \in V} {\deg(v)} \leq k $ which is, if we say that we have AT MOST $k-1$ leaves (I used the contradiction method to prove) \begin{align} \sum_{v \in V} {\deg(v)} &= \sum_{v \; \text{is a leaf}} {1} + \sum_{v \; \text{is not a leaf}} {\deg(v)} \\ &\leq (k-1) + k(n-k+1) \\ &= 2k - k^2 + kn -1. \end{align}

But that obviously tells us nothing. All extra information I know is that in a tree the sum of all degrees is $2|E| = 2(n-1) = 2n - 2$ so somehow I should get to an inequality/equality regarding $n$ only.

Any help is appreciated

Solution 1:

Let me give you a hint.

Start off by proving that every tree with at least two vertices must have at least 2 leaves.

Now, if the maximum degree is $k$, then there is a vertex $v$ of degree $k$. Consider the graph obtained by deleting $v$ from your tree. What does it look like? Prove that it is a collection of $k$ non-empty trees.

Consider each of these components. If the component has only one vertex, then this vertex was a leaf in the original graph: its only neighbor was $v$.

If the component has two or more vertices, then by the first claim it must have two leaves. Of these, only one could have been connected to $v$, since otherwise they form a cycle; hence at least one of them must have been a leaf in the original tree.

So, we get at least one leaf from each of the $k$ components of the new graph.

Solution 2:

Let the maximum degree be $k$. Start at a vertex of degree $k$ and travel away from it. There are $k$ possible choices of starting edge, each of which leads to at least one leaf. The leaves must be distinct, for otherwise there would be a cycle.