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