# Characterizations of operation that take a path and produce a star in a tree

I was looking at this operation in a tree, and try to relate it to the diameter of the tree.

Pick a path of length $m$, so let it be $v_1v_2\ldots v_mv_{m+1}$. Remove all the edges in the path, and add edge $v_1v_j$, where $2 \leq j\leq m+1$. It is easy to see the resulting graph is still a tree.

Intuitively, it replace a long path with many smaller paths.

I conjecture the longest path in a tree of $n$ vertices after doing this operation $k$ times, $i$th time act on a path of length $l_i$, is at most $n-\sum_{i=1}^k l_i + k$.

I have a hard time proving it or show a counterexample, because it is not easy to come up with a characterization of the tree after each operation. It is possile the longest path does not change at all in a sequece of operations.

-
If the tree is a path of length $n$, and you apply the operation to that path, you get a star, in which the longest path is of length $3>n-n+(1-1)=0$. – Brian M. Scott Apr 8 '12 at 18:48
Aha, how did I missed that. I measure the length of a path by the number of edges. In that case we have 2>1. so I think one small change make it work. Simply have +k instead of +(k-1). – Chao Xu Apr 9 '12 at 3:14
If you’re measuring the path length by edges, you want to change the path in the second paragraph to $v_0v_1v_2\dots v_m$, so that it has $m$ edges instead of $m$ vertices. – Brian M. Scott Apr 9 '12 at 3:15
aha I see, thanks. fixed. – Chao Xu Apr 9 '12 at 3:24

I believe that I’ve found a counterexample to the conjecture. Consider the tree shown below:

                        1
|
2--3--4--5
|
6


Perform your operation on the path $2345$, taking $5$ as the ‘centre’:

                        1  2
|  |
3--5
|  |
6  4


Now perform it again on the path $1352$, taking $2$ as the ‘centre’:

                              1
|
6--3--2--5--4


We have $n=6$, $l_1=l_2=3$, and $k=2$, so $n-(l_1+l_2)+k=2$, but the third graph has a path of length $4$.

-
A good counterexample! Indeed doing this one can create longer path than before. However I wonder what happens if we give a ordering to the vertices, and one must pick the smallest vertex as the 'center'. – Chao Xu Apr 12 '12 at 14:53