Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

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

share|improve this answer
    
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.