Graph Theory: Show that if $G$ is a tree with the maximum degree $\geq k$, then $G$ has at least $k$ vertices of degree $1$. 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
 A: 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.
A: Let $n$ be the number of nodes, and $n_1$ the number of nodes with degree one. Then we have $n-1-n_1$ nodes of degree at least $2$. 
We know that the sum of the degrees of all the nodes is $2n-2$, so we have:
$$k+2(n-1-n_1) +n_1 \le 2n-2$$
which simplifies to
$$n_1\ge k.$$
A: While that concept is true and may be provable, there's a much simpler method. If we add together the degrees of every vertex, we get twice the number of edges.
Suppose there are $n$ vertices, maximum degree at least $k$. If we have at most $k-1$ vertices of degree 1, then we have one vertex that must be at least $k$, and the other $n-k$ vertices must be all at least 2.
This gives a total sum of at least $1\times(k-1) + 2\times(n-k) + k\times1 = 2n-1$, so the total number of edges must be at least $n$, meaning we don't have a tree.
