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
Best Answer
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.