木の中心が直径上に存在すること・中心を見つけるアルゴリズム

• 木の中心が直径上に存在すること
• 中心を見つけるアルゴリズム

について書きます。

木の中心とは「各頂点への距離の最大値」が最小になる頂点 (の集合) です。
頂点 $v$ から各頂点への距離の最大値を $ E(v) $ と書きます。つまり、

$$ E(v) = \max_u\{\mathrm{dist}(v, u)\} $$

です。
頂点間の距離はそれらの間にある辺の本数です。
そして $E(v) = \min_u\{E(u)\}$ であるとき、頂点 $v$ は木の中心であるといいます。

言葉の感じから、中心は木の直径 (を与える $2$ 頂点を結ぶパス) の真ん中あたりにありそうな気がしてきます。
実際そうです。
$x, y$ を最遠点対とします。つまり、$d = \mathrm{dist}(x, y)$ は直径 $\max_{u}\{E(u)\}$ に等しいとします。
このとき、$x$ から $y$ の方向へ $\lfloor d/2 \rfloor$ 進んだ頂点を $c$ とすると $c$ は中心で $E(c) = \lceil d/2 \rceil = \mathrm{dist}(c, y)$ です。
任意に頂点 $v \neq c$ をとって $E(c) \le E(v)$ を示します。
そのためには、ある一つの $u$ に対して $E(c) \le \mathrm{dist}(v, u)$ が言えれば十分です。右辺は $E(v)$ 以下だからです。
さて、$v-x$ パスおよび $v-y$ パスを考えると、どちらかのパス上に $c$ があります。

v-x パス上に c がある場合

• $v-c-x$ となっている場合、$\mathrm{dist}(v, c) \ge 1$ より $\mathrm{dist}(v, x) \ge 1 + \mathrm{dist}(c, x) = 1 + \lfloor d/2 \rfloor \ge\lceil d/2 \rceil = E(c) $
• $v-c-y$ となっている場合、$\mathrm{dist}(*, *) \ge 0$ より $\mathrm{dist}(v, y) = \mathrm{dist}(v, c) + \mathrm{dist}(c, y) \ge \mathrm{dist}(c, y) = E(c) $

$E(c) \le E(v)$ が言えたので $c$ は中心です。
また、$d$ が奇数のとき、つまり $\lfloor d/2 \rfloor \ne \lceil d/2 \rceil$ のとき $c$ から $y$ 側に $1$ 進んだ頂点もまた中心です。
証明は上の議論を $x$ と $y$ をひっくり返してコピペすればいいです (たぶん) 。

中心は直径上に存在し、その個数は $1$ つか $2$ つであることが分かりました。
それでは、$3$ つ以上存在しないことを示しましょう。
木の頂点数が $2$ 以下の場合はあきらかなので頂点が $3$ つ以上あるとします。
このとき、葉をぜんぶ取り去ったあとに残る木において、中心はもとの木の中心と一致します。
小さくなった木の任意の頂点 $v$ について $E(v)$ はもとの木でのそれより $1$ 小さいからです。
$E(v) = \max_u\{...\}$ を達成する $u$ は葉じゃないとおかしいですもんね。
残された木がまだ $3$ つ以上の頂点を持っていたら、葉を取り除く操作を繰り返します。
頂点が $2$ つ以下になっていたらそれら ($1$ つ or $2$ つ) が中心です。
ありがたいことに、この証明は具体的に中心の見つけ方を教えてくれています！
半径 $\min_u\{E(u)\}$ が欲しいだけなら、はじめにやったように直径を $2$ で割って切り上げするのが早いと思います。
直径は dfs を $2$ 回するアレで求まります。
この方法なら、終わったあとに直径の両端が手に入っているはずなので、パスをたどって中心を見つけてもいいです。

葉を削除していって中心を求めるアルゴリズムの実装例 (C++) を以下に示します。
直径を求める問題でむりやり使ってみるとこうなります：提出

#include <queue>
#include <vector>

using namespace std;

vector<int> centers(const vector<vector<int>> &g) {
  int n = g.size();
  vector<int> deg(n, 0);
  for (int i = 0; i < n; i++) {
    for (auto j : g[i]) {
      deg[j] += 1;
    }
  }
  queue<int> leaves;
  for (int i = 0; i < n; i++) {
    if (deg[i] == 1) leaves.push(i);
  }
  vector<int> removed(n, false);
  int remaining = n;
  while (remaining > 2) {
    queue<int> nxt;
    while (leaves.size() > 0) {
      auto leaf = leaves.front();
      leaves.pop();
      removed[leaf] = true;
      remaining -= 1;
      for (auto j : g[leaf]) {
        deg[j] -= 1;
        if (deg[j] == 1) nxt.push(j);
      }
    }
    leaves.swap(nxt);
  }
  vector<int> ret;
  for (int i = 0; i < n; i++) {
    if (not removed[i]) ret.push_back(i);
  }
  return ret;
}

最後の仕事です。
上で「葉を取り除く操作を繰り返す」と言いましたが、葉はつねに存在するんですか？という質問に答えないといけません。
頂点数を $n \ge 3 $ とします。

• 木には葉が $2$ つ以上存在する

  葉の個数を $k$ とおく。辺数は $n - 1$ だから次数の和について

  $$\displaystyle k + \sum_{\mathrm{deg}(v) \ge 2} \mathrm{deg}(v) = 2 (n-1)$$

  が成り立つ。シグマは葉以外の頂点 $n - k$ 個に対して和をとっている。したがって、上の式より $k + 2(n - k) \le 2(n - 1)$ だから $k \ge 2$ である。

参考

Every tree has either one or two center | Tutorials on Mathematics