If a tree has $n$ vertices, then it must have a path with at least $k$ vertices or at least $n/k$ leaves

Question

Prove the following statement:

If a tree has $n$ vertices, then it must have a path with at least $k$ vertices or the tree must contain at least $\dfrac{n}{k}$ leaves.

---

My thoughts:

I kind of get why this is true, since if the longest path has $k-1$ vertices, then at best you can have one vertex in the middle with paths of length $\dfrac{k-1}{2}$ going out from it in $\dfrac{2n}{k-1}$ directions for a total of $\dfrac{2n}{k-1}$ leaves.

However, I can't seem to give a rigorous proof of this - any hints?

Answer 1

Hint: Arbitrarily choose some "root" vertex $r$ in $G$. For every leaf $\ell\in G$, there is a unique path $p(\ell)$ from $r$ to $\ell$. Every vertex in $G$ is contained in one of these paths, that is, $$ V(G)=\bigcup_{\ell\text{ is a leaf}}p(\ell) $$

Addendum: You can prove a stronger result. If you choose the root $r$ to be the midpoint of any path of maximal length, then the same proof shows that any tree whose longest path has $k$ vertices will have at least $\frac{n}{\lceil k/2\rceil}$ leaves.

Answer 2

We can restate the requirements as $\ell p > n$ for a tree with $\ell$ leaf nodes out of $n$ total and maximum path involving $p$ vertices.

By inspection, the claim is true for the trivial case of $n=2$. For $n\ge 3,$ the shortest possible path involves $3$ vertices, and must involve a non-leaf vertex.

Suppose that a tree has longest path involving $p$ vertices. Find a maximum length path from each leaf, and arrange in descending order. Now consider each such path in turn, discarding those from leaves that have already been visited and considering how many so-far unvisited vertices are involved each time. This involves at most $p/2$ new vertices per new leaf considered, since if the path goes to a leaf already considered, the new portion cannot be more than $p/2$ or there would be a longer path, and if it goes to an unvisited leaf we can split the new vertices between the two leaves.

After visiting $m$ leaves we thus have visited no more than $mp/2$ different vertices total, and clearly this still holds after visiting all $\ell$ leaves, when all vertices have been visited - that is, $\ell p>n$ as required.

---

P.S. Maybe "all vertices have been visited" is not quite obvious. This seems apparent to me but a proof would take a little more effort than seems appropriate here.