木における最長パス（またはその長さ）を木の直径といいます。 木の直径は次のように求められます。
- 木の頂点 $r$ を任意に選ぶ
- $r$ から最も遠くにある頂点 $x$ を求める （DFS などを使う）
- $x$ から最も遠くにある頂点 $y$ を求める（DFS などを使う）
- $x$ と $y$ を結ぶパスが直径になる
このアルゴリズムの正当性は以下のことから言えます。
木の任意の頂点 $r$ から最も遠くにある点 $x$ は直径の端点になる。
今回はこの性質の証明を絵で描いてみました。式だけだと追うのが難しかったので絵にしてみました。
