GATE CSE 2021 Set 2 | Question: 1

Question

Let $G$ be a connected undirected weighted graph. Consider the following two statements.

• $S_1$: There exists a minimum weight edge in $G$ which is present in every minimum spanning tree of $G$.
• $S_2$: If every edge in $G$ has distinct weight, then $G$ has a unique minimum spanning tree.

Which one of the following options is correct?

• A. Both $S_1$ and $S_2$ are true
• B. $S_1$ is true and $S_2$ is false
• C. $S_1$ is false and $S_2$ is true
• D. Both $S_1$ and $S_2$ are false

Comments

in this question s1 is false and s2 is true but in GO answer key it is showing s1 true s2 false

---

Counter-example for S1 → Consider a triangle, with each of the 3 edge-weights being equal – now 3 MSTs are possible here and in each of the 3 MSTs, 1 edge misses out, so no minimum weight edge is present in all the 3 MSTs.

---

$S1:$ is $true$ if edge weight are distinct  and $false$ if edge weight are same  

$S2:$ is $true$

Answer 1

We can think of running the Kruskals algorithm for finding the Minimum Spanning Tree on graph $G.$

While doing that, we sort the edges based on their weight and start selecting edges from the smallest weight $(w_{\text{small}}$ for example).

Problem with $S_1$:  If we have multiple copies of $w_{\text{small}}$, then a specific $w_{\text{small}}$ weighted edge is not guaranteed to be selected by Kruskals algorithm.

$S_2$ is Correct: If the sorted order of the edges contains only distinct values, Kruskals algorithm will always select a unique set of edges resulting in a unique minimum spanning tree.

Correct option: C.

Comments

going through a bunch of comments makes me feel that still, a min weight edge is definitely present as per your counterexample hence statement S1 is still holding as true...

---

I think the following.

“There exists a minimum weight edge” – about a specific edge

and ..

“There exists a minimum weight “ – about a specific weight value

---

Converse of S2 is NOT TRUE.

Answer 2

S1 is false -->If G has all edges with equal weight , then not possible,

S2 is true

Comments

@Arjun Sir, @himanshu19

In S1 we are given specifically that,

"There exists a Minimum weight edge in G"

By english grammar terms it should mean that only one edge of minimum weight in G.

As we have exists and not exist.

Also, they have written "a" minimum weight edge in G.

So, shouldn’t answer be Both True by this thought process?

---

Logically there exists doesn't mean a single edge, 2,3,4... even if all edges are same weight it is still true

---

I think this are english statements grammatically, “There exists a”, automatically imply that?

Also, “exists” is used with singular noun, as mentioned here.

 

Also, they would have said: “There exist minimum weight edges in G, among them one is present in every minimum spanning tree of G”. or something along that line to consider multiple minimum edge weights.

---

I don't know dude, the G in Gate doesn't stand for grammar, but the A stands for aptitude, if they really justified it like this I would be sad.

---

There always exists a minimum weight edge which is present in every spanning tree of G
Both should be true

---

i think both should be true,

bcoz even if you say there is a graph with all edges with same edge weigth, still the statement truly holds, bcoz really there exists a minimum weight edge in G which is present in all MSTs

bcoz all have the same “min” edge weight.

<is my point clear?>

@Arjun Sir plz check this…!

@Arjun Sir,@zxy123

---

Let’s wait, but I still don’t think you are correct.

Having same weight and being same are completely different.

---

Yes we should wait..but i dont think there is any thing wrong in my interpretation, bcoz you cannot deny to the said case in my earlier comment either?

---

I am denying it but you are not accepting it, lol :p

---

yes himanshu you are correct.

:)

---

Both Statements should be correct if “min” edge weight is concerned.

For Statement 1 to be False, I think a more precise and strong language in the question is needed.

---

opt A should be correct as per my opinion if min edge weights are taken into account.

@Arjun sir

---

In that case, S1 is trivially true & ruins the question. :)

---

I think it’s wrong to say ruins the question, it was already 1-marker, and any “serious” aspirant know about the concept where multiple MSTs are possible. May be it was expected to be straight forward and many ruined it by thinking more complicated cases.

---

Yes, it depends on the perspective.

---

Can you provide any example that given minimum edge is not selected. Kruskals will always pick the smallest edge weight. So that minimum edge will always be selected even though there exist multiple minimum spanning tree.

Answer 3

S1: “There exists a minimum weight edge in G”

There can be two interpretations of this statement-

1) There exists a specific minimum weight edge which must be present in all minimum spanning trees of the graph.

2) There exists atleast one minimum weight edge which is present in every minimum spanning trees of the graph.

In either case S1 will be false statement. Let me prove this using two examples.

For case 1

 

Here edge AB is not present in two of the possible minimum spanning trees.

For case 2

Here no edge is common between the two possible minimum spanning trees of the graph. That is there does not exist atleast 1 edge which is present in the two possible spanning trees.

So we can clearly state that Statement 1 is False.

S2: “If every edge in G has distinct weight, then G has a unique minimum spanning tree.”

This statement is obvious since if edge weights are distinct there will always be a distinct edge set and only 1 minimum spanning tree possible. Which is True

Correct Answer C

Answer 4

Since in S1 its not mentioned about the uniqueness of weights, assume in the graph where all edges have equal weights, then all the weights are minimum and not all minimum weights are included in spanning tree. Hence S1 is false.

 

In S2 all the edge weights are unique this means only 1 possible combination is there for making the spanning tree. Hence true.

So option C is correct

Comments

The answer should be, both S1 and S2 true. as per the language given in the question, you can’t make assumptions, i.e. there are multiple minimum weighted edges.