# 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

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.

• The new graph doesn't need to have $2k$ vertices of degree 1. Consider a star graph where the central vertex is connected to $k$ vertices. Deleting it leaves $k$ vertices of degree 0. Jun 23, 2013 at 17:31
• Fair again. Time to drink more coffee... Jun 23, 2013 at 17:32
• There, that should do it. Jun 23, 2013 at 17:34
• Wow, an amazing way. Thank you so much. Jun 23, 2013 at 17:51

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.

• Thank you, but it is a bit missing, you need to prove that why if the leaves we get to are not distinct then there is a cycle. Jun 23, 2013 at 18:12
• There is a unique path between any two vertices in a tree. Jun 23, 2013 at 18:49

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$$

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 .$$

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

• I looked carefully to see how you might be proving "a better result". It seems to me you are claiming "if a tree has a vertex of degree $m$ then tree has at least $m$ leaves". Compare the Question: "Prove that in a tree with maximum degree $k$, there are at least $k$ leafs[sic]". Since you are posting a reply to a three year old Question, there is no reason to hurry your Answer. If you see a way to prove a stronger claim, that would be interesting, but I don't see how your claim is any stronger. Mar 16, 2017 at 0:46