GATE CSE 2000 | Question: 2.18

Question

Let $G$ be an undirected connected graph with distinct edge weights. Let $e_{max}$ be the edge with maximum weight and $e_{min}$ the edge with minimum weight. Which of the following statements is false?

• A. Every minimum spanning tree of $G$ must contain $e_{min}$
• B. If $e_{max}$ is in a minimum spanning tree, then its removal must disconnect $G$
• C. No minimum spanning tree contains $e_{max}$
• D. $G$ has a unique minimum spanning tree

Comments

Emax edge in this graph/path can be Emin in other path/graph.

 

---

@Rishi Reddy no, it wont be possible because they have mentioned that Emax be the edge with maximum weight among distinct edge weights. So the case you are saying is not possible

The only way Emax is part of spanning tree is when Emax is the cut-edge(bridge)

So option c is false

---

2
     A-----------------B
     |
3   |
     |
     C-----------------D   
                  4

for option C

Answer 1

C the case should be written as "may or may not", to be true.

D will always be true as per the question saying that the graph has distinct weights.

Correct Answer: $C$

Comments

@minal

NO, definitely not. pendant vertex can’t always be of maximum edge right?

---

let e_max = E

in G , there is a cut such that E is a bridge and the 2 partitions form connected components in the MST.

In such a cut, if there are bridges other than E, then its weight should be lesser than E (by def)

however, as E is in the MST, it must also be the lightest bridge. Hence, E is the only bridge.

Thus removal of E will disconnect the graph.

---

option c: if there is a lighest weight edge in spanning tree then it must included in mst but if there is a heaviest edge in spanning tree then it may or maynot included in mst but here in option c it is saying that heaviest edge must not contain in mst this is false because there is a chance.so option c is false

Answer 2

option a is true. e_min should be there in all MST

option b is true - if e_max there that means that is the only edge reachable to one of the incident vertices of it. Otherwise we will select lesser weight edge incident on that vertex, Hence its removal will disconnect G

we cannot infer whether c  and d are true always. sometimes they can be false

Comments

sir it is not always true that we get unique spanning tree

its counter example is in above image

here possible mst is 5+8+10=23

and 6+7+20=23

---

but in the given graph minimum spanning tree cost is not 23.

minimum spanning tree is 5+6+7 = 18

What you are commented is about there are two different spanning tree of same cost.

but they are not minimum spanning tree. MInimum spanning tree is a spanning tree with minimum cost.

Please note that option D is G has a unique minimum spanning tree

---

If G is the unique min spanning tree just bcz edge weights are unique then why not option 1 is true..

Answer 3

Option 1 :- Every minimum spanning tree of G must contain $e_{min}$.

Kruskal's algorithm always picks the edges in ascending order of their weights while constructing a MST of G. So yes , it is true.

 

Option 2 : -  If $e_{max}$ is in a minimum spanning tree, then its removal must disconnect G .

$e_{max}$ would be included in MST if and only if , $e_{max}$ is a bridge between two connected components , removal of which will surely disconnect the graph.

Option 3 :- No minimum spanning tree contains $e_{max}$.

Contradictory statement , already proved in option 2 that $e_{max}$ can be in MST. Thus option 3 is false.

Option 4 :- $G$ has a unique minimum spanning tree.

G has unique edge weights , so MST will be unique . In case if edge weights were repeating , there could've been a possibility of non-unique MSTs.

Thus it is true.

Answer 4

Only option C is False.

Comments

but according to the question all  edges should be distinct

---

Yes it is... i have given all gate question possible into 1 page.

---

If weights are not distinct then every min sp tree has an min edge is false

 

Answer 5

Given in the question:

• $G$ is an undirected connected graph with distinct edge weights
• Maximum weighted edge: $e_{max}$
• Minimum weighted edge: $e_{min}$

Lets go through each option one by one to select false statement.

Option A: Every minimum spanning tree of $G$ must contain $e_{min}$

• Conclusion: True
• Reason: 
  • If we apply Kruskal’s algorithm, it says to sort the edge in ascending order
  • And pick the minimum, which shall definitely be $e_{min}$ in this case
  • Therefore, MST of $G$ must contain $e_{min}$

Option B: If $e_{max}$ is in a MST, its removal must disconnect G

• Conclusion: True
• Reason:
  • Only reason why $e_{max}$ would be in a MST is that it must be a bridge
  • Hence its removal should disconnect the original Graph G

Option C: No MST contains $e_{max}$

• Conclusion: False
• Reason:
  • Not necessarily, in fact we can see from Option B that it can be in a MST

Option D: G has a unique MST

• Conclusion: True
• Reason:
  • Edge weights are distinct, so MST will be unique
  • In case of same edge weights, we could have derived multiple MSTs

Therefore, only False statement is C.

 

Answer 6

Since given the edge weights are distinct hence

1.Every mst must contain the min edge weight .If in the question it was mentioned that edge weights are not distinct then it might be possible that there may be multiple edges with min edge weight.

2.A MST will contain emax only if it is acting as a bridge in a graph be in any graph either with distict weights or non-distinct weights

3.This statement is true because of the above staement

4.Since edge weights re distinct hence we have a unique MST.But remeber the converse is not true .If the grpah has a unique MST then it is not necessary that it might have distinct edge weights