1
$\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!

  • 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.2012-11-23

2 Answers 2

4

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.

  • 0
    That helps, thanks a lot!2012-11-23
6

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.

  • 0
    Great explanation, thanks!2012-11-23