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
The problem is the following:
Give an example of a graph that has a unique minimum spanning tree but for every cut of the graph, there is not a unique light edge crossing the cut.
I am trying to find such a graph, but I have not find any example. Is it possible to have such a graph? If not, why?
No.
Here is a proof. Suppose $G$ is a weighted undirected graph such that for every cut of the graph, there is not a unique lightest edge crossing the cut.
Let $M$ be a (or "the" in case it is unique) minimum spanning tree of $G$. Let $v$ be a leaf node of $M$. Consider the cut $\{\{v\},V\setminus \{v\}\}$ of $G$. Since $M$ is spanning, it contains an edge $m$ that crosses the cut. There are at least two edges of the minimum weight that cross the cut. Suppose one of them is $c_1\not=m$. Let graph $M'$ be the same as $M$ but with $m$ replaced by $c_1$. It is a routine to show that $M'$ is also an MST. So we know $G$ has two different $MST$s, $M$ and $M'$.
This negative conclusion can be seen as an corollary of the characterization theorem of the uniqueness of MST as stated in this answer. Here is the relevant part of that theorem.
(Uniqueness of MST by cut) Let $G$ be a weighted undirected graph. $G$ has a unique MST if and only if every edge is either the unique edge of minimum weight crossing some cut or never an edge of minimum weight to cross any cut.
Now let us assume $G$ is a graph of at least 2 nodes such that for every cut of the graph, there is not a unique light edge crossing the cut. Let $C$ be a cut of $G$. Let $e$ be the edge of minimum weight in the cut-set of $C$. Because $e$ is not the unique edge of minimum weight to cross any cut, we see that $G$ cannot have a unique MST.
If there is not a unique light edge crossing any cut, it means that every node has at least 2 edges of minimum weight. If you use Prim's algorithm to build your MST which is:
Grow the tree, adding nodes one by one.
On each step, select the minimum weight
edge leading to a new node.
You realise that whatever is the starting node, you have at least 2 choices. If the MST was unique, there would be leaf nodes having only one possible edge. Therefore there are several possible MST.
I found this answer in a book:
Consider a graph with 3 vertices a,b,c and weights w(a,b) = w(a,c) = 1 and w(b,c) = 2. The graph has a unique minimal spanning tree (containing edges (a,b) and (a,c)), however cut ({a}, {b,c}) doesn’t have a unique light edge crossing the cut.
I hope it helps!
