Graphs: Prove that G has a spanning tree with diameter k

Question

Suppose graph G has spanning trees with diameters $2, l$. for each $2 < k < l$ prove that G has a spanning tree with diameter $k$

Any hints how to start the proof?

Answer 1

The spanning tree with diameter $2$ can only be a star: a single central vertex with $n-1$ leaves. So that part of the condition is telling you that there exists some vertex $v$ adjacent to every other vertex.

Take the spanning tree $T$ with diameter $l$. If you repeat the following process:

1. Find a vertex $w$ of $T$ whose distance (in $T$) from $v$ is as large as possible. (This will necessarily be a leaf.)
2. Change $T$ by removing $w$, and adding it again as a leaf from $v$.

What happens to the diameter?