GATE Overflow Test Series | Algorithms | Test 2 | Question: 15

Question

A cut $S= (V - S)$ of an undirected graph $G=(V,E)$ is a partition of $V.$ We say that an edge $(u,v)\in E$ crosses the cut $(S, V - S)$ if one of its endpoints is in $S$ and the other is in $V - S.$ An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut. Note that there can be more than one light edge crossing a cut in the case of ties.  Mark all the correct options.

• A. If an edge is contained in some Minimum Spanning Tree (MST), it is a light edge crossing some cut
• B. $\{(u,v): \text{there exists a cut $(S, V - S)$ such that $(u,v)$ is a light edge crossing it} \}$ forms a MST
• C. A graph $G$ has a unique MST if for every cut, there is a unique light edge crossing the cut
• D. If a graph has a unique MST, then for every cut of the graph there is a unique light edge crossing the cut

Comments

Brilliant question. Cleared so many concepts.

---

unique in Option D gets ignored … very good question.

Answer 1

Option B is false as this will include multiple light edges crossing a cut if they are having the same weights.
Option D is also false as can be seen in the counter example given below.


Here, for the cut set $\{a\}, \{b,c\}$ we have two light edges of weight $1$ but there is a single MST $b-a-c.$

Comments

For more reference:

https://gateoverflow.in/302810/gate2019-38

---

can someone explain opt A and B in brief?

as per my understanding in A,if graph has 4 vertex abcd and cut is of those 4 single vertex{a,b,c,d} set then any edge we include it will be of cut only as all vertex are seperate in cut, is my understanding correct?

and for B i am not getting.