Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Prove that if $G$ is a tree with $\Delta$ being the maximum degree of the vertices, and $k$ $\leq \Delta$, then G has at least $k$ leaves.

I was given the hints that first prove $\left| {{V_1}(G)} \right| \ge 2 + (\Delta - 2)\left| {{V_\Delta }(G)} \right|$ and finish the proof by showing that $\left| {{V_1}(G)} \right| \ge k$ but I don't really see the point. Any help is appreciated, thanks!

share|improve this question
1  
What is $k$? If $k$ is any arbitrary number below $\Delta$ then are you just trying to show that the tree has at least $\Delta$ leaves? –  EuYu Nov 23 '12 at 6:09
    
Yes, $k$ is any number not exceeding $\Delta$, but why is that? –  drawar Nov 23 '12 at 6:14
1  
Well, if it holds for any $k\le \Delta$ then it must hold for $\Delta$ itself as well. That means the tree has at least $\Delta$ leaves. –  EuYu Nov 23 '12 at 6:15

2 Answers 2

up vote 3 down vote accepted

Identify a vertex of greatest degree and consider sawing the tree into $\Delta$ branches from that vertex. You then have a forest of $\Delta$ smaller trees. You have introduced exactly $\Delta$ new leaves to the forest. What is an easy lower bound on the number of leaves that the entire forest must have?

Edit: Your hint seems to be an off-shoot of the above. Applying the above method once will prove that $|V_1| \ge \Delta$. But strangely, your hint actually proves something stronger (without mentioning it).

Suppose you have $|V_\Delta|$ vertices of degree $\Delta$, then splitting the branches the first time will generate $\Delta$ new leaves with a total of $\Delta -1$ new trees. A second split again introduce $\Delta$ new leaves with another $\Delta - 1$ new trees. If you split each of the |V_\Delta| vertices of degree $\Delta$ then you end up with $1 + (\Delta - 1)|V_\Delta|$ trees in your forest and a total of $\Delta|V_\Delta|$ new leaves. Each tree in your forest has at least two leaves, therefore your entire forest has at least $$2 + 2(\Delta - 1)|V_\Delta|$$ total leaves, of which $$2 + 2(\Delta - 1)|V_\Delta| - \Delta|V_\Delta| = 2 + (\Delta - 2)|V_\Delta|$$ are original to your tree. So your hint proves a bound not just for a single vertex of degree $\Delta$, but an arbitrary number. This bound is easily seen to be optimal.

share|improve this answer
    
That's nice, but is there any method that fits the hints given? –  drawar Nov 23 '12 at 6:35
    
@drawar See update to the answer. –  EuYu Nov 23 '12 at 6:58
    
That helps, thanks a lot! –  drawar Nov 23 '12 at 11:08

Every subgraph of a tree is a tree. Let $v \in V(G)$ be a vertex of degree $\Delta$. Since $G$ is tree implies $v$ is a cut-vetex. Consider the $\Delta$ $v$-lobes. Each $v$-lobe is a tree with $v$ as a leaf. Since all trees with more than 1 vertex have at least 2 leaves, each $v$-lobe contains another leaf. Thus there are at least $\Delta$ leaves.

Or without the notation: There is a vertex that 'branches out' in $\Delta$ ways. Each of these branches must end somewhere, and cannot connect back to the other branches since that would create a loop. Thus each of these $\Delta$ branches must have at least one leaf, hence the graph has at least $\Delta$ leaves.

share|improve this answer
    
Great explanation, thanks! –  drawar Nov 23 '12 at 6:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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