# Graph theory: spanning tree diameter

For $2 \le k \le n − 1$, prove that the $n$-vertex graph formed by adding one vertex adjacent to every vertex of $P_{n−1}$ has a spanning tree with diameter $k$.

I know that the diameter of a tree is the length of its longest path from an example in my text (West), so that gives me length of $n-2$ in this path before I add one vertex. So does adding a vertex that connects to each of the edges extends the length of the path by $1$?

## 1 Answer

This is what the graph looks like in the $n-1=9$ case: A spanning tree is a subgraph that is both (a) a tree and (b) contains every edge.

Here's an example of a spanning tree in the above graph: There will be many others. The task set in the question is to find examples of spanning trees of diameter $d$ for $d \in \{2,3,\ldots,n-1\}$, for all $n \geq 1$.

Hint: The brown edges in the following diagram illustrate examples of spanning trees of diameter $2,\ldots,6$, respectively, in the case $n-1=6$. I suggest you try to generalize this construction. (Note the diameter $n-2$ case is special.)

• Suppose we label the added vertex x and label the vertices on the original path v_1, ..., v_n-1. Now choose a spanning tree from x to one of the endpoints of P_n-1, either v_1 or v_n-1. Then the diameter of the spanning tree would be <= n-1. Actually, it seems to me that it would be n-1. – PhiB Sep 12 '13 at 18:49
• (Choosing a spanning tree from $x$ to one of the endpoints of $P_{n-1}$ doesn't really make sense.) A spanning tree is a subgraph that is (a) a tree and (b) contains every vertex. So, in the above illustrations, we delete the pink edges to get a spanning tree. But there will be many other spanning trees I've not listed. – Rebecca J. Stones Sep 12 '13 at 18:58
• I am so sorry; I did not state my intent very well. I want to choose a spanning tree that begins at x and travels through each vertex, ending at an endpoint, so the path would be x, v_1, v_2, ..., v_n-1. (Or you could begin with x, v_n-1, ... and go the other way). In your picture, the final spanning tree is the one I had in mind. – PhiB Sep 12 '13 at 19:03
• Yes, that's one spanning tree, and it has diameter $n-1$ (but that still leaves the diameter $2,\ldots,n-2$ cases open). – Rebecca J. Stones Sep 12 '13 at 19:06
• Create the first spanning tree by creating a path from x to v_1 by traveling through each v_i from v_n-1 to v_1. This tree will have diameter n-1. Next, create a path from x to v_1 by traveling through each v_i from v_n-2 to v_1 and create a path from v_n-2 to v_n-1. This path will have diameter n-2. From here on, create paths from x to v_1 by traveling through each v_i from v_n-k to v_1, 2<=k<n-2, and by creating a path from x to each v_i for any v_i not contained in the previous path. These trees will have diameters n-3, n-4, …, 2. We have a spanning tree with diameter k for 2 <= k <= n-1. – PhiB Sep 12 '13 at 20:29