HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

MST: Is there such an example of a graph with unique mst and not unique light edge?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
suchuniquegraphwithexampleedgelightmstandthere

Problem

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?

Solution

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.

Code Snippets

Grow the tree, adding nodes one by one.
On each step, select the minimum weight
edge leading to a new node.

Context

StackExchange Computer Science Q#103331, answer score: 2

Revisions (0)

No revisions yet.