I am trying to prove the following property on graphs:
Let $G$ be a graph with a weight assigned to each edge and suppose that there are no two different edges with equal weight. Show that there is a unique minimum spanning tree of $G$
This is what I've tried so far:
Suppose there are at least two distinct minimum spanning trees $A_1$ and $A_2$ of $G$. Then there exists $e_2 \in \text{edges}(A_2 \setminus A_1)$. Then the graph $T = A_1 + e_2$ has a unique cycle $C$ that contains $e_2$. If there is an edge $e \in C$ with weight greater than the weight of $e_2$, then $T' = T – e$ is a tree with total weight less than $A_1$, which is absurd by definition of minimum spanning tree. Now, suppose $e_2$ is the edge with maximum weight on this cycle, take $e' \in C$ such that $e' \not \in A_2$ (note that there must be such an edge since otherwise $A_2$ would contain the cycle $C$). Then $\text{weight}(e') < \text{weight}(e_2)$ (here I am using the hypothesis that all edges of $G$ have different weights) and if we define the graph $T'' = (A_2 – e_2) + e'$, then $T''$ is a spanning tree with total weight less than the total weight of $A_2$, which is absurd since $A_2$ was a minimum spanning tree of $G$.
I would like to know if this solution is correct, any suggestions to improve or generate an alternative solution are welcomed. Thanks in advance.
Best Answer
If you set $e_2$ to be the (unique) edge with minimum weight in $E(A_1 \setminus A_2)$ $\cup E(A_2 \setminus A_1)$ [and then assume WLOG that $e_2 \in A_2)$], the existence of such an $e'$ in the cycle in $A_1 + \{e_2\}$ would itself be a contradiction. And so the uniqueness of the Minimum-Weight Spanning Tree would follow.
What @Batominovski said in his comment.