For a given metric $d$ on a finite (vertex) set $V$, how can I bound the largest edge length in $O(|V|)$? While (wlog) assuming that the smallest edge length is at least $1$.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
HINT: You’ll need to use the triangle inequality. Its basic form says that for any $x,y,z\in V$,
Generalize this: for any $x,y_1,\dots,y_n,z\in V$,
A proof by induction on $n$ seems indicated.