2
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ Allright, I think I'm on the right track, just need some confirmation. Suppose $v$ is not in the furthest pair, then there's another pair $(x,y)$, forming the greatest pair. However, since there's a unique path from $x$ to $y$ (we're dealing with a tree), $v$ must be on that path. Since $d(x,y) = d(x,v) + d(v,y)$ and $d(u,v) < d(x,y)$ we also have that either $d(x,v) \ge \frac{1}{2} \cdot d(u,v)$ or $d(y,v) \ge \frac{1}{2} \cdot d(u,v)$ holds, and by consequence, there's a path from $u$ to $x$ or from $u$ to $y$ with $d(u,x)>d(u,v)$ or $d(u,y)>d(u,v)$. Contradiction! $\endgroup$
    – MathRookie
    Commented Mar 28, 2015 at 13:11
  • $\begingroup$ Why must $v$ lie on the path from $x$ to $y$? – Note that the "furthest pair" is not uniquely determined; only the largest occurring distance is. $\endgroup$ Commented Mar 28, 2015 at 16:04
  • $\begingroup$ That was my only concern. It's indeed not necessarily true, but was necessary for my proof. Back to square one. Any suggestions? $\endgroup$
    – MathRookie
    Commented Mar 28, 2015 at 16:40

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ Thank you for this answer, although I don't really get what you mean with "the symmetry of $x,y$". We don't know what $x,y$ are, then how do we know they are symmetric? And why is this important anyway? $\endgroup$
    – MathRookie
    Commented Mar 29, 2015 at 8:25
  • $\begingroup$ That means, if $P_{[w,v]}$ and $P_{[x,w]}$ do have some common edge, then $P_{[w,v]}$ and $P_{[y,w]}$ must have no common edge, and we carry out the argument with "$y$". $\endgroup$
    – Salomo
    Commented Mar 29, 2015 at 11:12
  • $\begingroup$ I fully understand now. Thank you. $\endgroup$
    – MathRookie
    Commented Mar 30, 2015 at 18:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .