[Math] Graph theory: spanning tree diameter

graph theory

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$?

Best Answer

This is what the graph looks like in the $n-1=9$ case:

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:

An example spanning tree

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$.

n-1=6 case

I suggest you try to generalize this construction. (Note the diameter $n-2$ case is special.)