In any tree, what is the maximum distance between a vertex of high degree and a vertex of low degree?

1.2k Views Asked by At

In any undirected tree $T$, what is the maximum distance from any vertex $v$ with $\text{deg}(v) \geq 3$ to the closest (in a shortest path sense) vertex $y$ with $\text{deg}(y) \leq 2$? That is, $y$ can be leaf.

It seems to me that this distance can be at most $\dfrac{\text{diam}(T)}{2}$, and furthermore that the maximum distance will be attained from a graph center. Is this true? There's probably simple argument for it somewhere.

2

There are 2 best solutions below

2
On BEST ANSWER

In answer to the first version of the question (between any $v$ and any $y$):

------------------------------------------------------<
y is at the left, v is at the vee

The answer to the second version of the question is yes. Suppose that $v$ were more than $\frac{D}{2}$ away from all leaves, where $D$ denotes the graph diameter. Pick two of the branches leading from $v$. Each of them contains at least one leaf. The shortest path between these leaves passes through $v$, and is of distance more than $D$, being the sum of two distances each more than $\frac{D}{2}$. This is a contradiction.

The bound given is tight, by considering the Y graph on four vertices.

0
On

In your second question (shortest path to vertex of degree $\le 2$), the bound $\operatorname{diam}(G) / 2$ holds, simply by noticing that the ends of the longest path in a tree are leaves, and the "worst" that a graph can do is have the vertex of degree $3$ or higher right in the center. But in fact, this holds for the shortest path from any vertex of to vertex of degree $1$.

Can we do better? No, in fact. Take a look at a tournament bracket, for example (just delete the leaves on one side to create a unique center). Viewed as a tree, all the vertices are of degree $3$ except for the leaves, which are all at least distance $d/2$ from the center of this modified graph.