Let \(G=\left ( V,E \right )\) be \(any\) connected, undirected, edge-weighted…

Conclusion: Only the statement that the minimum spanning tree of G is always unique is necessarily true; the statement that shortest paths between any two vertices are always unique is not necessarily true.

1. Proof of uniqueness of the minimum spanning tree: Suppose all edge weights are positive and distinct. For contradiction, assume there exist two different minimum spanning trees T1 and T2. Consider the set of edges that belong to exactly one of T1 or T2 (the symmetric difference). Let e be the edge in this set with the smallest weight. Without loss of generality, e is in T1 but not in T2. Adding e to T2 creates a cycle. Every other edge on that cycle must have weight greater than the weight of e (because e was the smallest edge in the symmetric difference and weights are distinct). Removing any heavier edge from the cycle yields a spanning tree with total weight strictly less than T2, contradicting the minimality of T2. Therefore no such pair T1, T2 can exist, and the minimum spanning tree is unique.

2. Shortest paths need not be unique: Distinct edge weights do not prevent two different paths from having the same total length. Simple counterexample: take three vertices u, v, w forming a triangle with edge weights w(u,w)=2, w(w,v)=3, and w(u,v)=5. The direct edge between u and v has weight 5, while the two-edge path u–w–v has total weight 2+3=5. Thus there are two different shortest paths between u and v of equal length, so uniqueness of shortest paths is not guaranteed.