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

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.