グラフは木であり, そのうち距離が最大となるような 2 頂点を選ぶ問題である. すなわち, 木の直径を求めれば良い.

どこか 1 つの頂点を選び, そこから BFS で最も遠い頂点を求める. 次にその頂点から BFS で最も遠い頂点を求める. この 2 頂点間の距離が木の直径となる.