Cho một cây vô hướng ~T = (V, E, w)~ thỏa mãn ~w > 0~

Gọi ~L \subset V, L \ne \emptyset~ là một tập nút đặc biệt của cây

Gọi ~d_i~ là độ dài đường đi đơn dài nhất từ nút ~i~ đến một nút trong tập ~L~. Nói cách khác, ~d_i = \max_{x \in L} f(x,i)~ với ~f: V \times V \rightarrow \mathbb{R}, (x,y) \mapsto \text{độ dài đường đi đơn từ } x \text{ đến } y~

Lưu ý nếu ~i \in L~ thì ~d_i \ne 0~ hoàn toàn có thể xảy ra do có thể tồn tại đường đi đơn giữa hai nút trong tập ~L~.

Chọn một nút ~r~ thỏa mãn ~\forall u \in V: d_r \leq d_u~ là nút gốc của cây.

Nếu nút ~x~ là tổ tiên của nút ~y~, ta kí hiệu ~x \rightarrow y~

Chứng minh rằng ~\forall x,y \in V, x \rightarrow y: d_x \leq d_y~

Bổ đề

~\forall x \in V, x \ne r: \forall y \in L, x \rightarrow y: d_x \ne f(x,y)~

Chứng minh bổ đề

Chọn nút ~x, y~ bất kì sao cho ~x \in V, x \ne r, y \in L, x \rightarrow y~

Do ~\forall u \in V: d_r \leq d_u~ và ~x \in V~, ~d_r \leq d_x~

Giả dụ ~d_x = f(x,y)~.

Do ~r~ là gốc, ~r \rightarrow x~. Do ~\begin{cases} r \rightarrow x \\ x \rightarrow y \end{cases}~ nên ~f(r,y) = f(r,x) + f(x,y)~.

Do ~y \in L~ và ~d_r = \max_{i \in L} f(r,i)~, ~d_r \geq f(r,y)~

Do ~w > 0~, ~f(r,x) > 0~ nên ~f(r,x) + f(x,y) > f(x,y)~

Do ~\begin{cases} d_r \geq f(r,y) \\ f(r,y) = f(r,x) + f(x,y) \\ f(r,x) + f(x,y) > f(x,y) \\ d_x = f(x,y) \end{cases}~ nên ~d_r > d_x~

Tuy nhiên, điều này trái với ~d_r \leq d_x~. Do đó, giả dụ ban đầu sai, tức ~d_x \ne f(x,y)~

Do cách chọn ~x, y~, ta kết luận được

~\forall x \in V, x \ne r: \forall y \in L, x \rightarrow y: d_x \ne f(x,y)~

và đây là điều phải chứng minh

Quay lại bài toán

Chọn ~x,y \in V~ bất kì sao cho ~x \rightarrow y~.

Nếu ~x = r~, ta có điều phải chứng minh

Nếu ~x \ne r~, theo bổ đề đã chứng minh ở trên, ~d_x = f(x,t)~ với ~t \in L, x \nrightarrow t~.

Ta có thể chọn nút ~a = \text{lca}(x,t)~ thỏa mãn ~a \rightarrow x~, ~a \rightarrow t~ và ~f(x,t) = f(x,a) + f(a,t)~

Do ~\begin{cases} a = \text{lca}(x,t) \\ x \nrightarrow t \\ x \rightarrow y \end{cases}~ nên ~a = \text{lca}(y,t)~

Do đó ~f(y,t) = f(y,a) + f(a,t)~

Do ~\begin{cases} a \rightarrow x \\ x \rightarrow y \end{cases}~ nên ~f(y,a) = f(y,x) + f(x,a)~

Vì thế nên ~f(y,t) = f(y,x) + \Big(f(x,a) + f(a,t)\Big) = f(y,x) + f(x,t) = f(y,x) + d_x~

Do ~w > 0~ nên ~f(y,x) \geq 0 \Rightarrow f(y,x) + d_x \geq d_x~ và vì thế ~f(y,t) \geq d_x~

Do ~t \in L~ và ~d_y = \max_{i \in L} f(y,i)~, ~d_y \geq f(y,t)~

~\begin{cases} f(y,t) \geq d_x \\ d_y \geq f(y,t) \end{cases} \Rightarrow d_y \geq d_x~

Do cách chọn ~x, y~, ta có thể kết luận

~\forall x,y \in V, x \rightarrow y: d_x \leq d_y~

Đây là điều phải chứng minh.