1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.