I found the statement that in every simple, undirected and connected graph with $v$ vertices, there is one vertex that has a maximum distance of $\frac{v}{2}$ to all other vertices.
I have limited the statement to trees because if it is true for trees it should be true for all simple, undirected and connected graphs as adding edges to trees creates circles which can only shorten the distance but not increase it.
I am fairly certain that the statement is correct but I am unsure how to proof it. I was thinking about showing it for a tree with only two leaves and thereby a maximum sum of distances between the vertices and showing that even in this case it holds, so it should hold for any other tree. Does that make sense?
Best Answer
Given a tree with $v$ vertices, let $a$ and $b$ be two vertices such that the distance $D$ between them is maximal (i.e. there are no two vertices with a greater distance between them.) Clearly $D \le v-1 \,$.
Suppose $D$ is even, and let $c$ be the middle vertex on the path from $a$ to $b$. Clearly the distance from $c$ to $a$ and to $b$ is $\frac{D}{2} \,$. If there were any vertex (call it $f$) whose distance to $c$ was larger than $\frac{D}{2} \,$, then the distance from $a$ (or $b$) to $f$ would be greater than $D$, contradicting the original assumption that the distance between $a$ and $b$ was maximal. Thus vertex $c$ has a maximum distance of $\frac{D}{2} \le \frac{v-1}{2} \,$ to every other vertex.
The case when $D$ is odd can be proven in a similar way.