Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Given a connected, undirected, weighted graph $G$, the following "cut condition"
For any partition of the vertices of $G$ into two subsets, the minimum-weight edge with one endpoint in each subset is unique.
is not necessary for $G$ to have a unique minimum spanning tree.
However, is this "cut condition" sufficient for $G$ to have a unique MST?
Related post: Is this "cycle condition" sufficient for unique minimum spanning tree?
Answer my own question: The answer is from here.
For every cut of $G$, the unique light edge crossing the cut must be part of every MST of $G$. Consider the set $T$ of edges, containing the unique light edge crossing each cut $C$ of $G$. Then, we know that $T$ is a subset of every MST.
Now we can show that $T$ must be equal to every MST.
Because there is exactly one edge of $T$ crossing every cut of $G$, the graph $(V, T)$ must have exactly one connected component: if there were two unconnected components $V_1$ and $V − V_1$, then the cut $(V_1, V − V_1)$ would not be crossed by any edge of $T$, which contradicts the definition of $T$. In addition, $T$ cannot contain any cycles: the heaviest edge on a cycle in $T$ cannot be the unique lightest edge in any cut. Then $T$ itself must be a spanning tree of $G$. Because $T$ is a subset of all minimum spanning trees of $G$, it must be the unique MST of $G$, as any additional edge added to $T$ would form a cycle, making it no longer be a tree.
