On the intercluster distance of a tree metric

Bang Ye Wu
Theoretical Computer Science
Volume 369, Issues 1-3 , 15 December 2006, Pages 136-141
http://dx.doi.org/10.1016/j.tcs.2006.07.056

無向グラフG=(V,E)の頂点部分集合V1,V2に対して，V1とV2の間の平均距離を
\sum_{u\in V1}\sum_{v\in V2}d(u,v)/(|V1||V2|)と定義する．
(ただし，dは最短パス距離である．)
このとき，Gが木であるならば，V1とV1の間の平均距離とV2とV2の間の平均距離の和がV1とV2の平均距離の2倍以下になることを証明している．
論文では言及されていないが，この「2倍」というのがタイトになる例は簡単に作れる．