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

Gọi ~s, t \in V~ là hai đầu mút của đường kính của ~T~

Chứng minh rằng: Đường đi đơn dài nhất trên ~T~ xuất phát từ một nút ~u \in V~ là đường đi từ ~u~ đến ~s~ hoặc đường đi từ ~u~ đến ~t~

Chứng minh

Chọn ~u \in V~ bất kì.

Đặt ~u~ làm gốc cây ~T~

Giả dụ đường đi đơn dài nhất trên ~T~ xuất phát từ ~u~ không là đường đi từ ~u~ đến ~s~ và cũng không là đường đi từ ~u~ đến ~t~ mà là đường đi từ ~u~ đến ~v~ với ~v \in V, v \ne s, v \ne t~.

Đặt ~a = \text{lca}(v,s), b = \text{lca}(s,t)~

Do ~a \rightarrow s~ và ~b \rightarrow s~, một trong hai trường hợp sau sẽ xảy ra:

Trường hợp 1: ~a \rightarrow b~

Khi đó, ~\begin{cases} a \rightarrow b \\ b \rightarrow t \end{cases} \Rightarrow a \rightarrow t~

Ta có: ~f(u,v) > f(u,t) \Rightarrow f(u,a) + f(a,v) > f(u,a) + f(a,t)~ (do ~a \rightarrow v~ và ~a \rightarrow t~) ~\Rightarrow f(a,v) > f(a,t)~

Do ~a \rightarrow b \rightarrow t~, ~f(a,t) \geq f(b,t)~

Ta có: ~f(s,t) = f(s,b) + f(b,t) \leq f(s,a) + f(a,t) < f(s,a) + f(a,v) = f(s,v)~

Điều này nghĩa là đường đi từ ~s~ tới ~t~ không là đường kính của ~T~ (do có đường đi từ ~s~ tới ~v~ dài hơn), trái với giả thiết ban đầu

Trường hợp 2: ~b \rightarrow a~

Đầu tiên, ta cần chứng minh ~lca(v,t) = b~.

~\begin{cases} b \rightarrow a \\ a \rightarrow v \end{cases} \Rightarrow b \rightarrow v~

~b = \text{lca}(s,t) \Rightarrow b \rightarrow t~

Giả dụ tồn tại ~c \in V~ sao cho ~c \rightarrow v~ và ~c \rightarrow t~ và ~b \rightarrow c~. Do ~a,b,c \rightarrow v~ và ~b \rightarrow c~, hoặc ~c \rightarrow a~ hoặc ~a \rightarrow c~.

Nếu ~c \rightarrow a~ thì với việc ~a \rightarrow s~, ~c \rightarrow s~. Do ~c \rightarrow s~ và ~c \rightarrow t~ và ~b \rightarrow c~, ~b \ne \text{lca}(s,t)~ nên trường hợp này không thể xảy ra.

Nếu ~a \rightarrow c~ thì do ~c \rightarrow t~, ~a \rightarrow t~. Điều này cộng với việc ~a \rightarrow s~ nghĩa là ~a~ là một cha chung của ~t~ và ~s~. Do ~b = \text{lca}(s,t)~, ~a \rightarrow b~, trái với điều kiện của trường hợp 2.

Do hai trường hợp đều không thể xảy ra, giả dụ tồn tại ~c \in V~ sai. Điều này đồng nghĩa với việc ~lca(v,t) = b~

Ta có:

• ~f(u,v) > f(u,s) \Rightarrow f(u,a) + f(a,v) > f(u,a) + f(a,s) \Rightarrow f(a,v) > f(a,s)~
• ~f(v,t) = f(v,a) + f(a,b) + f(b,t) > f(s,a) + f(a,b) + f(b,t) = f(s,t)~

Do đó, đường đi từ ~s~ đến ~t~ không thể là đường kính của ~T~, trái với giả thiết ban đầu.

Do cả trường hợp 1 và trường hợp 2 đều không thể xảy ra, giả dụ ban đầu sai.

Ta giờ có thể kết luận

~\forall u \in V:~ Một đường đi đơn dài nhất xuất phát từ đỉnh ~u~ là đường đi từ ~u~ đến ~s~, hoặc là đường đi từ ~u~ đến ~t~

Hệ quả của định lí:

• Định lí này chứng minh tính đúng đắn của thuật toán tìm đường kính của cây
• Để tìm một đường đi dài nhất xuất phát từ ~u~, ta có thể tìm đường kính từ ~s~ đến ~t~ rồi xét hai đường đi từ ~s~ đến ~u~ và từ ~t~ đến ~u~