1-2 距離・直径・中心

path長は非負整数であり、長さ0のpathは始点と終点が同じ場合に限るので1が従います。
無向graphでは $u$–$v$ pathを逆順にたどれば同じ長さの $v$–$u$ pathになります。最短値を両方向で比較すれば2を得ます。
最短 $u$–$v$ pathと最短 $v$–$w$ pathを続けると、$u$ から $w$ へのwalkが得られ、その長さは
$$ d_G(u,v)+d_G(v,w) $$
です。このwalkが頂点を繰り返すなら、その間の閉じた部分を削除すると、より短いか同じ長さの $u$–$w$ pathが得られます。最短 $u$–$w$ pathの長さはその長さ以下なので三角不等式が従います。□

長さ $k$ の $u$–$v$ pathは、同型により長さ $k$ の $\varphi(u)$–$\varphi(v)$ pathへ移ります。従って
$$ d_H(\varphi(u),\varphi(v)) \le d_G(u,v). $$
逆同型 $\varphi^{-1}$ に同じ議論を適用すると逆向きの不等式を得るため、等号です。□

半径は離心率の最小値、直径は最大値なので
$$ \operatorname{rad}(G)\le\operatorname{diam}(G) $$
です。
中心頂点 $c$ を一つ取り、任意の $u,v$ に三角不等式を使うと
$$ \begin{aligned} d_G(u,v) &\le d_G(u,c)+d_G(c,v)\\ &\le\operatorname{ecc}(c)+\operatorname{ecc}(c)\\ &=2\operatorname{rad}(G). \end{aligned} $$
すべての $u,v$ について最大を取れば
$$ \operatorname{diam}(G)\le2\operatorname{rad}(G) $$
を得ます。□

$s$ から $u$ への最短pathの後に辺 $uv$ を加えると、$s$ から $v$ への長さ $d(s,u)+1$ のwalkが得られます。従って
$$ d(s,v)\le d(s,u)+1. $$
$u,v$ を交換して
$$ d(s,u)\le d(s,v)+1 $$
も得ます。二式を合わせれば主張が従います。□

相異なる頂点 $u,v$ を取ります。
$u,v$ が $G$ の異なる連結成分に属するなら、$G$ では隣接しません。従って $\overline G$ では隣接し
$$ d_{\overline G}(u,v)=1. $$
$u,v$ が同じ成分に属するなら、非連結性から別の成分の頂点 $w$ を取れます。$G$ では $uw,vw$ のどちらも辺でないため、$\overline G$ では
$$ u-w-v $$
が長さ2のpathです。従って任意の二頂点間距離は高々2で、$\overline G$ は連結かつ直径高々2です。□

$x$ から $y$ へのpathは木のpath一意性によりただ一つです。$y$ が葉でないと仮定すると、$y$ にはpath上で $y$ の直前にある頂点以外の隣接頂点 $z$ があります。
木にcycleはないので $z$ は $x$–$y$ path上にはありません。従って一意な $x$–$z$ pathは $x$–$y$ pathへ辺 $yz$ を加えたもので
$$ d_T(x,z)=d_T(x,y)+1. $$
これは $y$ が最遠であることに矛盾します。ゆえに $y$ は葉です。□

木には少なくとも二つの葉がありますが、3頂点以上ならすべての頂点が葉になることはありません。従って少なくとも一頂点が残ります。
$T^\circ$ は木の部分graphなのでcycleをもちません。残った二頂点 $u,v$ を取ります。$T$ の一意な $u$–$v$ pathの内部頂点は、path上で二つの隣接頂点をもつため $T$ の葉ではありません。端点 $u,v$ も残った頂点です。従ってpath全体が $T^\circ$ に残り、$u,v$ は $T^\circ$ で結ばれます。ゆえに $T^\circ$ は連結で、木です。□

補題により、$x$ から最遠の頂点 $\ell$ は $T$ の葉です。$\ell$ の隣接頂点を $y$ とすると、3頂点以上の木では $y$ は葉でなく $T^\circ$ に残ります。従って
$$ \operatorname{ecc}_T(x) =d_T(x,\ell) =d_{T^\circ}(x,y)+1 \le\operatorname{ecc}_{T^\circ}(x)+1. $$
逆に、$T^\circ$ で $x$ から最遠の頂点 $z$ を取ります。$T^\circ$ が一頂点だけなら、その頂点 $z=x$ は元の木で少なくとも一つの葉と隣接しています。
$T^\circ$ が二頂点以上なら、$T^\circ$ 内で $x$ から最遠の $z$ は $T^\circ$ の葉です。$z$ は $T$ では葉でないため、$T^\circ$ での唯一の隣接頂点以外に、削除された葉 $\ell$ と隣接しています。どちらの場合も
$$ d_T(x,\ell) =d_{T^\circ}(x,z)+1 =\operatorname{ecc}_{T^\circ}(x)+1. $$
従って逆向きの不等式も成り立ち、離心率の式を得ます。
最後に $T$ の葉 $\ell$ とその隣接頂点 $y$ を取ります。$\operatorname{ecc}_T(\ell)\ge2$ です。$\ell$ 以外の任意の頂点 $z$ へのpathは $y$ を通るので
$$ d_T(y,z)=d_T(\ell,z)-1. $$
また $d_T(y,\ell)=1$ です。従って
$$ \operatorname{ecc}_T(y) =\operatorname{ecc}_T(\ell)-1 <\operatorname{ecc}_T(\ell). $$
葉は離心率を最小化しないため中心ではありません。□

1頂点の木ではその頂点が中心です。2頂点の木では両頂点の離心率が1で、二頂点とも中心です。
3頂点以上の木 $T$ では、直前の補題により葉は中心でありません。従って中心候補はすべて $T^\circ$ にあります。また $x\in T^\circ$ について
$$ \operatorname{ecc}_T(x) =\operatorname{ecc}_{T^\circ}(x)+1 $$
なので、$T$ で離心率を最小にする頂点と $T^\circ$ で離心率を最小にする頂点は同じです。すなわち
$$ \operatorname{Center}(T) =\operatorname{Center}(T^\circ). $$
葉削除のたびに頂点数は減り、残るgraphは木なので、この操作は有限回で1頂点または2頂点になるまで続きます。中心は各段階で変わらないため、最後に残る頂点集合が元の木の中心です。2頂点残る場合、残ったgraphは連結な木なので二頂点は隣接しています。□

二頂点以上の木で最長pathの両端は葉です。全葉を一度削除すると、最長pathの両端が一つずつ削られ、その内部に長さ $\operatorname{diam}(T)-2$ のpathが $T^\circ$ に残ります。従って
$$ \operatorname{diam}(T^\circ)\ge\operatorname{diam}(T)-2. $$
$T^\circ$ が一頂点だけなら、$T$ の全頂点はその一頂点またはそれに隣接する葉です。$T$ は3頂点以上なので異なる葉が二つあり、直径は2です。従ってこの場合は
$$ \operatorname{diam}(T^\circ)=0=\operatorname{diam}(T)-2. $$
$T^\circ$ が二頂点以上なら、その直径pathの両端は $T^\circ$ の葉です。各端点は $T$ では葉でないため、削除された葉と少なくとも一つ隣接しています。両端でその葉を一つずつ付けると、$T$ に長さ $\operatorname{diam}(T^\circ)+2$ のpathが得られます。従って
$$ \operatorname{diam}(T)\ge\operatorname{diam}(T^\circ)+2. $$
二つの不等式を合わせ、3頂点以上では
$$ \operatorname{diam}(T^\circ) =\operatorname{diam}(T)-2. $$
この操作を繰り返すと、直径が偶数なら長さ0の一頂点へ、奇数なら長さ1の一辺へ到達します。木の中心定理により最後に残る頂点が中心であり、元の任意の直径pathから両端を同数ずつ削った中央と一致します。□

$P_8$ の端点間距離は7で、これが直径です。中央の二頂点は端点までの最大距離が4で、他の頂点はそれより大きい離心率をもちます。従って
$$ \operatorname{diam}(P_8)=7,\qquad \operatorname{rad}(P_8)=4, $$
中心は第4・第5頂点です。
$C_9$ では各頂点から最遠の頂点までの距離は $\lfloor9/2\rfloor=4$ です。従って
$$ \operatorname{rad}(C_9) =\operatorname{diam}(C_9)=4, $$
全9頂点が中心です。□

1は $K_2$。半径・直径とも1です。
2は3頂点以上のstar。中心の離心率1、葉どうしの距離2です。
3は $P_4$。中央二頂点の離心率2、端点間距離3です。
4は $P_5$。中央頂点の離心率2、端点間距離4です。□

$u\in L_i$、$v\in L_j$ が隣接するとします。距離層の命題から
$$ |d(s,u)-d(s,v)|=|i-j|\le1. $$
従って辺があり得るのは $i=j$ または $|i-j|=1$ の場合だけです。特に $|i-j|\ge2$ なら辺は存在しません。□

元の各成分内では全頂点が隣接するので、補graphでは成分内に辺がありません。異なる二成分間には元の辺がないので、補graphではすべての交差辺があります。従って
$$ \overline G=K_{3,2}. $$
異なる側の頂点間距離は1、同じ側の相異なる頂点間距離は2です。各側に少なくとも二頂点あるため全頂点の離心率は2で
$$ \operatorname{rad}(\overline G) =\operatorname{diam}(\overline G)=2. $$
□

最初の葉は $a,e,g$ です。これらを削除すると、残る辺は
$$ bc,\ cd,\ cf $$
で、中心 $c$ と葉 $b,d,f$ からなるstarです。さらに $b,d,f$ を削除すると $c$ だけが残ります。従って中心は $\{c\}$ です。
$c$ から最遠の葉 $a,e,g$ までの距離はいずれも2なので半径は2です。葉 $a$ から $e$、または $a$ から $g$、$e$ から $g$ の距離は4なので直径は4です。□

自己同型 $\varphi$ は距離を保存します。従って
$$ \begin{aligned} \operatorname{ecc}(\varphi(v)) &=\max_{w\in V(G)}d(\varphi(v),w)\\ &=\max_{u\in V(G)}d(\varphi(v),\varphi(u))\\ &=\max_{u\in V(G)}d(v,u)\\ &=\operatorname{ecc}(v). \end{aligned} $$
二行目では $\varphi$ が全単射なので $w=\varphi(u)$ と書けることを使いました。離心率が半径に等しいという性質が保存されるため、中心集合は自分自身へ写ります。
頂点推移graphでは、一つの中心頂点を任意の頂点へ送る自己同型があります。中心性が保存されるので任意の頂点が中心です。□