Take the 2-minute tour ×

Assume that we have a metric space $(S,d)$ and points $a,b,c \in S$ which statisfy the following conditions:

  • for all $x \in S$, $d(a,x) \leq d(a,b)$,
  • for all $y\in S$, $d(b,y) \leq d(b,c)$.

Does the following statement follow from these two assumptions?

  • for all $x,y\in S$, $d(x,y) \leq d(b,c)$

In words: if $b$ is a furthest point from $a$ and $c$ is a furthest point from $b$, is $d(b,c)$ the maximum possible distance between points in $S$?

In case someone is interested in the motivation: I was trying to see how much graph structure is needed in the proof that using two BFSes we can find the diameter of a finite connected graph:

  1. Start from $a$ and find a vertex $b$ with maximum distance from $a$.
  2. Start from $b$ and find a vertex $c$ with maximum distance from $b$.
  3. $d(b,c)$ is the diameter of the graph.

The algorithm doesn't work correctly. Here is a counterexample:

enter image description here

share|improve this question
+1 Nice question, Kaveh. –  Babak S. Mar 23 '13 at 6:09

2 Answers 2

up vote 2 down vote accepted

In the plane let $a=c=\langle -1,0\rangle$, $b=\langle 1,0\rangle$, $x=\langle 0,z\rangle$, and $y=\langle 0,-z\rangle$, and let $S=\{a,b,x,y\}$. If $1<z<\sqrt3$, then $b$ is maximally far from $a$, $c$ is maximally far from $b$, and $d(x,y)>2=d(b,c)$.

share|improve this answer
what would be the best bound then? –  Mathematician Mar 23 '13 at 5:56
@Mathematician: Off the top of my head I see nothing better than the obvious one given by the triangle inequality: $$d(x,y)\le d(x,b)+d(b,y)\le 2d(b,c)\;.$$ –  Brian M. Scott Mar 23 '13 at 5:59
Thanks Brian for the example. ps: is it possible to have an example where the distances are all natural numbers? (or do you think it is better to ask a new question?) –  Kaveh Mar 23 '13 at 6:04
@Kaveh: You’re welcome. –  Brian M. Scott Mar 23 '13 at 6:07

Take the set of points to be the intersection of the following two circles in $R^2$ and the metric to the normal euclidean distance metric,


Take $a=(0,0),b=(1,0),c=(-1/2,0)$

These satisfy the conditions in the problem,

Now take the points of intersection of both the circles, these are $(-1/8,3\sqrt{7}/8),(-1/8,-3\sqrt{7}/8)$. The distance between these two point is $3\sqrt{7}/4$

$7>4\Rightarrow 3\sqrt{7}/4>3/2=d(b,c)$.

So we have a contradiction.

share|improve this answer

Your Answer


