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

Any example in support of c?

---

since all edge is distinct so emin must be tthere so true

option b is true.

..

remove of AE can give the disconnected G

Option C is false.

---

option B) is direct implication of option c) property of cut vertex

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

this is a really good question.

---

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

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.