(a) Lemma 1 on Page 5 can be proved with the sole use of the triangle inequality. To see this, let again $x_0$ and $y_0$ be such that $d(x_0,y_0)$ = d_{\max}$. Then we have $\sum_{\{x,y\} \subset X} d(x,y) \geq \sum_{x \in X \setminus \{x_0, y_0\}} ( d(x_0,x) + d(x,y_0)) + d(x_0,y_0) \geq (n-1) d(x_0,y_0)$. The last inequality follows from the triangle inequality, and the first one is obvious. (b) The statement of Lemma 2 on Page 6 should read $\sum_{x \in X} d(x,g) \leq n-1$. (It is actually very straightforward to see where you made the mistake in your proof. A counter-example to the $n/2$ bound is given by a triangle with equal length sides of length 1.) In consequence, some of the numbers in the inequalities on top of Page 7 change accordingly. (c) A different proof of (the corrected version of) Lemma 2 on Page 6 follows from the observation that $d(x,y)$ as a function of $y$ is convex. Therefore, $d(x,g)$ = d(x, \frac{1}{n} \sum_{y \in X} y) \leq \frac{1}{n} \sum_{y \in X} d(x,y)$. (d) Lemma 4 on Page 8 isn't quite correct either. For instance, suppose that $w_x = (n-1)/2$, and $n$ is even. Then the lhs is equal to $n/2 - 1$ whereas the rhs equals $n/2 - 1 + 1/2n$. Isn't difficult to correct either; in fact, in the proof of Lemma 5 on the same page you already use a different inequality.