Let T be tree, the pendant vertices of T cannot be central vertices.

198 Views Asked by At

enter image description here

Let $v$ be a pendant vertex and $v$ be a central vertex. So, $e(v)=r(G)=\max\{d(v,u):u \in V(G)\}$. Let $P$ be the longest path from $v$ with length $e(v)$. $e(v) \leq \{e(u):u \in V(G)\}[\because e(v)=r(G)] $ From the definition, I can draw the conclusion till here. please help me to proceed further.

2

There are 2 best solutions below

2
On

If $v$ is a pendant vertex, every path from $v$ must pass through its neighbour $w$. What does this tell you about $e(w)$?

(You need to assume $T$ has at least three vertices for the result to be true.)

0
On

Let $v$ be a leaf with neighbour $w$. Now, if $\xi = vv_1,\dots, v_ku$ is a minimal path from $v$ to some vertex $u$, necessarily $v_1 \in N(v) = \{w\}$. Thus every path from '$v$ goes through $w$', and we get a path of length $d(v,u) - 1$ from $w$ to $u$. In particular, $d(w,u) < d(v,u)$. Taking maximum on $u$,

$$ e(v) = \max_{u}d(v,u) < \max_ud(w,u) = e(w) $$

And so $v$ can not attain the minimum eccentricity of $G$.

Edit: as clarified by Especially Lime, the argument above strongly uses that $\xi$ has at least three vertices. If not, every path from $v$ is of the form $vw$, and so you get $K_2$ whose center is itself.