3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.


$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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