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
 A: 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.
A: Suppose , that there are $l$ leaves. You know , from theory , that it has exactly $|E|= n-1 edges$. Every vertex in a tree , that's not a leaf , should have a degree of max value k and at least 2. So we want to create a lower bound for l. So there should be at least one vertex of degree k , l vertexs of degree 1 ( the leaves) and (n-l-1) of degree $>=$ 2.
Then $2|E| =2(n-1)= \sum deg(v) >= l + (n-l-1)2 +k \rightarrow 2n-2l-2+k+l=2n-l+k-2<= 2n -2 \rightarrow -l +k <=0 \rightarrow l>=k$
A: 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.
A: More generally, if some vertex has degree $k$, then there are at least $k$ leaves, as the following proof shows.
The $k=1$ case is a tautology, so assume $k \ge 2$.
Let $n_d$ be the number of nodes of degree $d$, and let $n$ be the total number of nodes.  By counting nodes and edges, we have
\begin{align}
\sum_d n_d &= n \tag1 \\
\sum_d d n_d &= 2(n-1) \tag2
\end{align}
Combining $(1)$ and $(2)$ yields $$\sum_d d n_d = 2\left(\sum_d n_d-1\right).$$
Hence the number $n_1$ of leaves satisfies
$$n_1 
= 2 + \sum_{d\ge 2} (d-2) n_d 
\ge 2 + (k-2) n_k 
\ge 2 + (k-2) = k
.$$
A: Let $T = (V, E)$ be a tree with a vertex of degree $k$. Let $v_0$ be the vertex of degree $k$. Now let $v_i$ be a vertex such that $\{ v_0, v_i \} \in E(T)$ and $i \in \{ 1$, ... , $k \}$. Let $P_i$ be the path of maximum length in $T$ such that $v_0$ is the first vertex in the path and $v_i$ is the second vertex in the path. Note that in the path $P_i$, a subgraph of $T$, $deg_T(v_0) = 1$. Using the leaf lemma (every non-edgeless tree has at least $2$ nodes) and the fact that $P_i$ has no branches because it's a path, there exists exactly $2$ leaves in $P_i$. Furthermore, there exists $1$ leaf in the path such that the leaf is not $v_0$. In other words, the minimum number of leaves, $n_i$, in $P_i$—not including $v_0$—is $1$. Because $i \in \{1, ..., k\}$, we can take the sum $\displaystyle\sum_{i=1}^{k} n_i$ = $\displaystyle\sum_{i=1}^{k} 1= k$, we see that $T$ contains at least $k$ leaves (if you're wondering "Can't there be more leaves?", you would be correct, however, we only need to show the tree has at least $k$ leaves). One thing to note is that we can guarantee that all the counted leaves are distinct because if they weren't, we would either obtain a cycle in $T$ or a path longer than $P_i$, both of which are contradictions since cycles cannot exist in a tree and $P_i$ has been defined as a path of maximum length containing $v_0$ and $v_i$.
A: we can directly  prove a better  result if  a tree  has  a vertex of degree  m then tree has  at least m leaves  solution is simple  as tree on n vertices has  n-1 edges  sum of degrees of vertices in tree  is 2(n-1)  now  if r   is number of leaves in tree  then  we  have  n-r-1  vertices in tree whose degree  is at least  2
hence  we have  m+r+2(n-r-1) less than or  equal to 2(n-1)
that  would give   r is at  least m  i.e there are at least m leaves  
