2
$\begingroup$

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!

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$
    – EuYu
    Commented Nov 23, 2012 at 6:09
  • $\begingroup$ Yes, $k$ is any number not exceeding $\Delta$, but why is that? $\endgroup$
    – drawar
    Commented Nov 23, 2012 at 6:14
  • 1
    $\begingroup$ 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. $\endgroup$
    – EuYu
    Commented Nov 23, 2012 at 6:15

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Great explanation, thanks! $\endgroup$
    – drawar
    Commented Nov 23, 2012 at 6:33
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ That's nice, but is there any method that fits the hints given? $\endgroup$
    – drawar
    Commented Nov 23, 2012 at 6:35
  • $\begingroup$ @drawar See update to the answer. $\endgroup$
    – EuYu
    Commented Nov 23, 2012 at 6:58
  • $\begingroup$ That helps, thanks a lot! $\endgroup$
    – drawar
    Commented Nov 23, 2012 at 11:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .