ARC 108 F - Paint Tree

• 問題

主張: 与えられた木$T$の直径を$D$とし、長さ$D$のあるパスの端点$V_b, V_w$が黒、白に塗られているとする。また、黒に塗られた頂点同士の最大距離を$X$とし、距離$X$の黒に塗られた2頂点$A, B$が与えられているとする。このとき、パス$V_b - A$または$V_b-B$の少なくとも一方は長さ$X$である。

証明: パス$V_b - A, V_b-B$の両方の長さが$X$未満と仮定する。3頂点$V_b, A, B$の間にできる3つのパスに共通して含まれるただ1つの頂点を$c$とすると^[1]、$d(c, A) + d(c, B) = X$だから、$d(c, A), d(c, B)$の少なくともいっぽうは$X/2$以上である。$d(c, A) \ge X/2$としてよい。また、パス$V_b - A$が長さ$X$未満という仮定より

$$d(V_b, c) + d(c, A) < X$$

が成り立つから、$d(V_b, c) < X/2$が導ける。整理すると

$$\begin{aligned} D & \le d(V_w, c) + d(V_b, c) \\ & < d(V_w, c) + \frac{X}{2} \\ & \le d(V_w, c) + d(c, A) \\ & = d(V_w, A) \end{aligned}$$

$d(V_w, A) > D$が導かれたので、直径より長いパスが見つかったことになり、矛盾する。$\square$

---

1. https://en.wikipedia.org/wiki/Tree_(graph_theory)#Properties より、For any three vertices in a tree, the three paths between them have exactly one vertex in common (this vertex is called the median of these three vertices). というやつ。 ↩︎