k-center problem: proof for Gon algorithm gives a 2-approximation The $k$-center problem is where we a given a graph $G(V,E)$, an integer $k$, a distance metric $d$ and we want to find a subset $C\subseteq V$ (such that $|C|\leq k$) which minimizes the following function: $\max_{v\in V}\min_{c\in C}d(v,c)$.
I am trying to understand the proof that the $Gon$ algorithm is a 2-approximation. The algorithm arbitrarily selects the initial center and loops for $k-1$ iterations, where at each iteration it adds the vertex which is furthest away from its nearest center as a new center.
The full proof that this algorithm gives a 2-approximation is described in Gonzalez, Clustering to minimize the maximum intercluster distance. The cost of the optimal solution is $OPT(V)$ and they describe the term &quot;$(k+1)$-clique of weight $h$ for $V$&quot;:

Set $T$ is said to form a $(k+1)$-clique of weight $h$ if the cardinality of set $T$ is $k + 1$ and every pair of distinct elements in $T$ are at least $h$ units apart.

The part that I don't understand is the following lemma:

Lemma 2.1: If there is a $(k+1)$-clique of weight $h$ for $S$, then $OPT(V)\geq h$.

My question is, what is the proof for this lemma?
If $k+1$ vertices are at least $h$ units apart, then no ball of diameter $&lt; h$ can cover two of these vertices, hence you would need at least $k+1$ balls.
Since you want to have at most $k$ balls, $h$ must be at least the minimum distance of the $k+1$ vertices (pairwise).
Another way of phrasing it would be:

If you have a set $T$ of $k+1$ points, and at most $k$ balls of diameter $h$, then at least one ball must contain two points.  Let $d$ be the shortest distance between two vertices in $T$ (the two closest vertices).  Then $h \geq d$.


Taking the contra-positive of the lemma:  If $\text{OPT} &lt; h$, then you cannot have $k+1$ points that have pairwise distance $\geq h$, or in other words, if  $\text{OPT} &lt; h$ then

Any set with pairwise distance at least $h$ has at most $k$ vertices
Any set with at least $k+1$ vertices has a pair with distance less than $h$.