Is there a tree $T$ such that $\text{diam}(T) \geq k$, where $k$ is the number of vertices with degree less than 3?

Question

Let $T$ be an undirected tree, let $d$ be the diameter of $T$, and let $s$ be the number of vertices in $T$ with degree less than 3. Recall the diameter of a graph is the length of the longest shortest path in $T$.

Consider the star graph $S_n$ on $n$ vertices. It is easy to see that the difference between $d$ and $s$ can be arbitrarily large. In this case, $d$ is always 2, but we can make $s$ how ever large we wish. In a path graph, $s-d=1$.

Is it possible to construct a tree where $d$ is greater than or equal to $s$? I don't think it is, but is there a simple argument to show it?

Answer 1

Direct proof:

• Consider any of the longest paths in the tree (it consists of $d$ edges and $(d+1)$ nodes).
• If we remove the edges of this path from the tree, we get a forest of $(d+1)$ trees, each of which has at least one leaf.
• Since removing the edges decreased the degree of each node by at most $2$, all these leaves had degree smaller than 3 in the original tree.
• Thus, $s\geq d+1$.

(and the path graph shows that this bound is tight).