1
$\begingroup$

Let there be a tree with at least two vertices. One vertex has degree $k$ and the other has degree $l$. Prove that such tree has at least $k + l - 2$ leaves.

My logic is that from one vertex you can reach at least $k$ leaves and from the other vertex you can reach at least $l$ leaves. But how exactly would I prove that you have to subtract $2$? Is it because if you start from one of the given vertices and go through the second one, then one of the leaves will be a duplicate?

|cite|improve this question
$\endgroup$
  • $\begingroup$ If you start from one of the vertices and follow a path of vertices to the second, you have discovered a cycle. And cycles are not allowed in trees. $\endgroup$ – Matthew Leingang May 13 at 18:00
2
$\begingroup$

In the tree $T$ there's a path from the vertex $v$ of degree $k$ to the vertex $w$ of degree $l$. Let this path start with the edge $e$. There are $k-1$ other edges from $v$, and one can walk from $v$ starting at any of these edges and reach a leaf. This accounts for $k-1$ leaves. Likewise start at $w$ to reach $l-1$ further leaves.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ A relevant (I think) addition is that the path from $v$ to $w$ is unique in a tree. So OP's concern about following a branch along an edge other than $e$ from $v$ and accidentally ending up at $w$ won't happen. $\endgroup$ – Matthew Leingang May 13 at 18:04

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.