The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
2.6k views

Let $G$ be any connected, weighted, undirected graph.

  1. $G$ has a unique minimum spanning tree, if no two edges of $G$ have the same weight.
  2. $G$ has a unique minimum spanning tree, if, for every cut of $G$, there is a unique minimum-weight edge crossing the cut.

Which of the following statements is/are TRUE?

  1. I only
  2. II only
  3. Both I and II
  4. Neither I nor II
in Graph Theory by Veteran (418k points)
edited by | 2.6k views
0
cut means cut set but not the cut edge !
0
the line is

"if for every cut of G ,there is a unique minimum weight edge crossing the cut,=> then G has a unique minimum spanning tree"
0

Cut set is the set of edges whose removal disconnect the connected graph..so do you not think that cut is also same as cut set and it is min cut set??

@Shaik Masthan

0

@Arjun @Digvijay Pandey please verify

+1

@Sankha Narayan Bose

e1 and e2 also a cutset, then is this diagram satisfying conditions mentioned in the question ?

0

@Shaik Masthan

I donot think it is telling about cut set. Because, if it is a cut set then can cut more than one edge, which is violation of spanning tree

right?

https://en.wikipedia.org/wiki/Cut_(graph_theory)

0

@Sankha Narayan Bose

Actually they are telling to remove minimum edge from a graph, (which they described as cut set) 

And after that removal, is it forming a MST? As minimum edge edge is unique , so it forming a unique spanning tree

0
Here they did not mention cut set..cut canbe bridge also..but if we can find atleast one counter example then is not it that statement can not be true..

Please let me know if my understanding is correct
0

@srestha They are asking about the original graph not the ones you get after cutting. 

0
They mean for any cut of the graph. Now what is a cut. Any partition of vertices of graph forms a cut. And for every cut if we choose the min edge passing that cut, then that gives us the mst of graph. Now they hv asked if this min for each cut is unique which implies we have a unique mst, so it's true.

2 Answers

+9 votes
Best answer

1. If edge weights are distinct then there exist unique MST.

2. If for every cut of a graph there is a unique light edge crossing the cut then the graph has a unique minimum spanning tree but converse may not be true.

Proof by contradiction:
Lemma: If an edge $e$ is contained in some minimum spanning tree, then it is a minimum cost edge crossing some cut of the graph.

Assume MST is not unique and there exist two MST's  $T_1$ and $T_2$
Suppose $e_1∈T_1$ but $e_1 \notin T_2$, if we remove $e_1$ from $T_1$, then we will have disconnected graph with two set of vertices $V_1$ and $V_2$. According to lemma $e_1$ is a minimum cost edge in the cut between $V_1$ and $V_2$.

Suppose $e_2∈T_2$ but $e_2 \notin T_1$, if we remove $e_2$ from $T_2$, then we will have disconnected graph with two set of vertices $V_1$ and $V_2$. According to lemma $e_2$ is a minimum cost edge in the cut between $V_1$ and $V_2$.

Because the minimum cost edge is unique implies $e_1$ and $e_2$ is the same edge. $e_1 \in T_2$ and $e_2 \in T_1$. We have chosen $e_1$ at random, of all edges in $T_1$, also in $T_2$ and same for $e_2$. As a result, the MST is unique.

So both are TRUE.

Answer is (C).

by Veteran (60k points)
selected by
0
It's a direct question from CLRS textbook, page number 630, Question 23.1-6. Another reason to do Exercise problems of standard text books :)
0

This example can be used to prove that converse of statement II is not true.  Cut is ({A,C},{B,D}).

The Minimum spanning tree is unique, however there are two minimum weight edges (A,B) and (A,D) having same weight crossing this cut.

+1 vote
If for every cut of a graph there is a unique minimum weight edge crossing the cut,
then the graph has a unique minimum spanning tree.

This statement is true and can be proved ea sily by contradiction.
by (363 points)
Answer:

Related questions

0 votes
1 answer
6
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,092 questions
55,322 answers
190,846 comments
86,218 users