GATE Computer Science (CS) 2022 Shift 1 Solved Paper

Question : 48 of 65

Marks: +1, -0

Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE ?

The edge with the second smallest weight is always part of any minimum spanning tree of G
One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G
Suppose S ⊆ V be such that S ≠ ϕ and S ≠ V. Consider the edge with the minimum weight such that one of its vertices is in S and the other in V \ S . Such an edge will always be part of any minimum spanning tree of G
G can have multiple minimum spanning tree

Validate

Go to Question:

Prev Question

Next Question