GATE CSE 2019 | Question: 38

Question

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?

• A. I only
• B. II only
• C. Both I and II
• D. Neither I nor II

Comments

number of ways to distribute k similar objects to n distinct set is : (n + k - 1)Ck

answer : (2+10-1)C10 * (2+15-1)C15 * (2+14-1)C14 = 2640.

---

For option 1 this is contradicting statement

---

Note that, it is used " if " in the statement but not " if and only if "

---

The claim should be true iff it is true for all graphs.

---

Even if the graph has multiple edges with same weight graph has unique MST

---

i am not getting what you want to deliver,

in the question they are saying,

if all edge weights are unique, then G has unique minimum spanning tree. ---- TRUE

Converse :-  If G has unique minimum spanning tree, then all edge weights are unique. ----- False

---

You are talking about the reverse implication -- not the given statement

---

got it.sorry for the inconvenience

---

no need of sorry, it's just a discussion !

---

@Arjun

why the following is not a counter example for second statement:

The cut has minimum unique weight but multiple MSTs.

---

You have to consider every possible cut sets as per the given statement.

---

@arjun why cut set and why not cut edge?

---

@Digvijay Pandey could you please the counter example given by sunil.

---

cut means cut set but not the cut edge !

---

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"

---

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

---

@Arjun @Digvijay Pandey please verify

---

@Sankha Narayan Bose

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

---

@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)

---

@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

---

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

---

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

---

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.

---

good read -

 

 https://stanford.edu/~rezab/discrete/Midterm/midtermsoln.pdf

---

2 is corman question

https://gateoverflow.in/151113/cormen

---

Most of students wouldn’t have attempted this.

---

Yes, because most of the students don't follow standard book exercises.

---

Yep, I did attempt correctly 2 years back also

---

For option 2 :

We can disconnect each and every vertex of graph or make it disconnected from the original graph by drawing a cut to incident edges on vertex and for every cut we are getting unique minimum weight edge passing through it that means we have at least one path to all vertices which contains unique minimum weight edges. So, MST must be unique.

---

Cut in Minimum spanning Tree:

https://www.baeldung.com/cs/minimum-spanning-tree-cut

---

what is wrong in my example please anyone explain ? 

bcoz in last example there is more than one spanning tree possible

---

@Ray Tomlinson they are asking about "EVERY" cut in 3rd graph {4,5},{4,6} edge is also a cut which have same weight.

Answer 1

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.

Why converse is not true always? 

https://stanford.edu/~rezab/discrete/Midterm/midtermsoln.pdf

So both statements in the question are TRUE.

Answer is (C).

Comments

What about this graph? Why edges with weight 2 on vertex F not considered according to definition 2? Source: Applied Gate test Series 

---

My bad! I missed the “converse may not be true” part!

---

The correcte counterexamples to falsify the converse of statement II are :-

“suppose the graph is a tree with 3 nodes, where both edges have cost 1. Let v be the node with degree two. Clearly the only spanning tree is the graph itself, but the cut between v and the two leaves contains two cost 1 edges, so the minimum cost edge is not unique across this cut.”

The converse of statement II is :- IF G  has a unique minimum spanning tree then   for every cut of G, there is a unique minimum-weight edge crossing the cut.

Its clearly not true for given example, the graph has unique MST but the cut at  2 doesnt have unique minimum  weight edge.

Answer 2

Statement 1 : True

Statement 2 : True. Explanation below.

For this I have an intuitive approach. This is not a formal mathematical proof but it occurred to me after thinking for quite some time. 

Please point it out if you think something is wrong.

Comments

Thanks man

---

thanks brother nice explaination

Answer 3

Statement 1 is true. Proof can be found easily.

---

The biggest confusion in Statement 2 is what is a cut? Is it cut set, or cut vertex, or cute edge?

Actually, a cut is anything that creates a partition, or "cut" in the set of vertices $V$ of a graph.

A cut $C=(S,T)$ is a partition of $V$ of a graph $G=(V,E)$ into two subsets S and T.

Notice "cut" is actually a set of two subsets.

One might say that cut is a cut set.

So, if for every cut set of a graph, there exists a unique minimum weight edge; then graph has a unique MST. True.

Why? Because the whole graph can be seen as the collection of these cut sets and from each cut set we can only pick the unique minimum weight edge.

---

 

Option C; both the statements are true.

---

 

Let G be a connected, undirected graph. A cut in G is a set of edges whose removal...

These wordings are taken from GATE 1999, Question Number 5.

Answer 4

Both the statements are true.

Statement (I) is based on how Kruskal’s algorithm works.

Statement (II) is based on how Prism’s algorithm works.

[Check the working/algorithm of each of them in CLRS and you can easily conclude that the two statements are two.]

Kruskal MST algorithm works by first sorting the edges in non-decreasing order of their weights. Then it chooses the edges taken in sorted order and adds them to the MST which the algorithm is forming if the edge being added does not form a cycle with the edges already in the MST in progress. Now if all the edge weights are distinct then while choosing an edge, Kruskal’s algorithm will not have any choice and the MST formed shall be unique.

Prim’s MST algorithm, works on the concept of cut. During its working it maintains two sets say $S$ [which contains the vertices included in the MST being formed] and the set $V[G]-S$ , which contains the vertices not yet incorporated in the MST being formed. Now set $S$ and $V[G]-S$ at each instant forms a cut. The algorithm works by incorporating the edge having the minimum edge weight between the two set $S$ and $V[G]-S$ and including it along with its end vertex $v$ in $V[G]$ into $S$. Now if every cut of the graph $G$ has unique edge weights, Prim’s algorithm shall not find options while choosing this edge.

Comments

Awesome explanation! Very Practical and Must be the best answer.