Let s and t be two vertices in a undirected graph G + (V, E) having distinct…

Key idea: the cut property of minimum spanning trees. The minimum-weight edge crossing any partition of the vertices must belong to every minimum spanning tree when all edge weights are distinct.

Proof sketch:

• Let the partition be (X,Y) with s in X and t in Y, and let e be the minimum-weight edge with one endpoint in X and the other in Y.

• Suppose, for contradiction, there exists a minimum spanning tree T that does not contain e.

• Adding e to T creates a unique cycle. That cycle must contain at least one other edge f that also crosses the partition (because e connects X to Y).

• Since e is the minimum-weight crossing edge, weight(e) < weight(f) (strict inequality follows from distinct edge weights).

• Removing f from the cycle yields a new spanning tree with strictly smaller total weight than T, contradicting the minimality of T.

Therefore, every minimum spanning tree must contain e.

Note: This conclusion does not imply the edge must lie on the weighted shortest path between s and t, on every s→t path, or on a weighted longest path; those are different objectives and can fail as shown by simple counterexamples.