2
$\begingroup$

Is there a necessary and sufficient condition for a minimum spanning tree to be unique?

I've searched and found a sufficient condition like this:

If each edge has a distinct weight then there will be only one, unique minimum spanning tree.

But I can't find a necessary condition!

$\endgroup$
-1
$\begingroup$

For any graph $G$, let $E'$ be the set of edges such that $e$ is the lightest (not necessarily unique) edge across some partition. $G$ has a unique MST $\iff$ $E'$ forms a spanning tree.

Proof:

If $G$ has a unique MST, then there are exactly $|V|-1$ edges which appear in every MST. Those edges must be unique lightest edges. Suppose not, and that there is an edge $e$ and $e'$ which are lightest edges across a cut. Then the MST in $G$ is not unique. This means that the edges in the MST are also all of the edges in $E'$, so $E'$ forms a spanning tree.

If $E'$ is a spanning tree, then it has $|V|-1$ edges which connect the graph. This means that every edge must be a unique lightest edge. Suppose not. Then across some edge, there exists $e$ and $e'$ which are both lightest edges, so $E'$ contains at least $|V|$ edges, and is no longer a spanning tree. By the Unique Cut Property, every lightest unique edge must appear in every MST.

$\endgroup$
1
  • $\begingroup$ This proof is erroneous: Consider the graph on the vertices (v1, v2, v3), where the edge weights are (v1, v2) = 1, (v1, v3) = 1, (v2, v3) = 2. Then the unique MST is (v1, v2) and (v1, v3), yet the two minimal edges to cross the partition (v1) and (v2,v3) are of the same weight (of 1) $\endgroup$ Oct 27 '20 at 8:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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