# 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 "$$(k+1)$$-clique of weight $$h$$ for $$V$$":

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 $$< 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} < h$$, then you cannot have $$k+1$$ points that have pairwise distance $$\geq h$$, or in other words, if $$\text{OPT} < h$$ then

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