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

Question

Consider a undirected graph $G$ with $n$ vertices and every edge weight being distinct. Edge $e_1$ is edge with minimum weight and edge $e_2$ is edge with maximum weight. Then, which of the following is/are FALSE? (Mark all the applicable options)

• A. Every minimum spanning tree of $G$ must contain $e_1$
• B. If $e_2$ is in a minimum spanning tree, then its removal must disconnect $G$
• C. No minimum spanning tree contains $e_2$
• D. $G$ has a unique minimum spanning tree if $e_2$ is in a minimum spanning tree

Answer 1

Since the edge weights are distinct every MST must contain the minimum weighted edge $e_1.$ Option A is TRUE.

The maximum weighted edge $e_2$ can be in the MST only if it is a cut-edge. So, its removal must disconnect the graph. Option B is TRUE, C is FALSE.

Option D is true as there's a unique MST if all edge weights are distinct.

Only option C is FALSE.

Comments

Got it...actually I was thinking of single source shortest path in which minimal cost can be found without the smallest edge in the graph....thanks btw👍

---

why option d is not in ans, it is false, consider an example, there is a triangle ABC with weight of all 3 edges equals to 1 and one more edge AD in this graph with weight 2, here AD has max weight which is 2 and it will be included in MST and also there are 2 MST. So option d is false and should be included in correct options

---

@Megha0809 it is given in the question that edge weight must be distinct.