How can i bound the largest edge length of an $n$-point metric in $O(n)$?

Question

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

Answer 1

HINT: You’ll need to use the triangle inequality. Its basic form says that for any $x,y,z\in V$,

$$d(x,z)\le d(x,y)+d(y,z)\;.$$

Generalize this: for any $x,y_1,\dots,y_n,z\in V$,

$$d(x,z)\le d(x,y_1)+\sum_{k=1}^{n-1}d(y_k,y_{k+1})+d(y_n,z)\;.$$

A proof by induction on $n$ seems indicated.