Show that if $G$ is a tree with $\Delta \geq k$, then $G$ has at least $k$ vertices of degree $1$.
I am guessing in this context Δ means the maximum degree. So the largest degree of any vertex in $G$ is $\geq k$. So eventually, all the edges coming off of the vertex with the maximum degree must end with a vertex of degree $1$ for $G$ to be a tree or there would be a cycle in $G$. I understand the concept of this problem, but I am having trouble putting it in graph theory terms. Can someone please help me do this?
Thanks
Best Answer
For every node in the tree, if it is of degree $n$, there are at least $n$ subnodes of degree 1 as below it.
Example: The root is of degree $k$, this means it has $k$ subnodes. Now, if no subnodes are connected to anyone of them, there are $k$ nodes of order 1, and we are done.
If some subnode has order $m > 1$, then there are $m$ subnodes below it, and by induction there will be at least $m$ nodes with order 1 connected to it, and $k-1+m$ nodes of order 1 in the whole tree.