I know in my mind that it's very obvious, but I just can't seem to prove the following statement:
Let $G$ be an undirected non-trivial tree with at least $3$ vertices. Let $u$ be an arbitrary vertex in that tree and let $v$ be the vertex furthest away from $u$. Prove that $v$ is in the furthest pair (the two vertices having the greatest distance between them) of $G$ by contradiction (thus, there must be another pair $(x,y)$ that is the furthest pair).
I'm assuming I have to use some inequalities using the distances $d(u,v)$, $d(x,v)$, $d(y,v)$ and $d(x,y)$. I just can't seem to figure out how these all relate to each other.
Any guidance towards the right direction will be much appreciated!
Suppose $v$ is not in any "furthest pair". Let $x,y$ be a furthest pair. For vertices $s,t$, we denote the $s$-$t$-path in the tree by $P_{[s,t]}$. Let $w$ be a vertex in $P_{[x,y]}$ with $d(u,w)$ minimum. By the symmetry of $x,y$, we can assume $P_{[w,v]}$ and $P_{[x,w]}$ have no common edge. By our assumption, $d(w,v)<d(w,y)$, otherwise $P_{[x,w]}$ would be a longest path in the tree. Then, $d(u,y)=d(u,w)+d(w,y)>d(u,w)+d(w,v)\geq d(u,v)$, contradiction to the choice of $v$.