13
$\begingroup$

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

$\endgroup$

5 Answers 5

16
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Calvin Lin
    Jun 23, 2013 at 17:31
  • 1
    $\begingroup$ Fair again. Time to drink more coffee... $\endgroup$ Jun 23, 2013 at 17:32
  • $\begingroup$ There, that should do it. $\endgroup$ Jun 23, 2013 at 17:34
  • $\begingroup$ Wow, an amazing way. Thank you so much. $\endgroup$
    – TheNotMe
    Jun 23, 2013 at 17:51
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – TheNotMe
    Jun 23, 2013 at 18:12
  • 4
    $\begingroup$ There is a unique path between any two vertices in a tree. $\endgroup$
    – Théophile
    Jun 23, 2013 at 18:49
1
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – hardmath
    Mar 16, 2017 at 0:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.