Exams › GATE › Technical

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?

1. The edge with the second smallest weight is always part of any minimum spanning tree of G.
2. One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G.
3. Suppose S ⊂ V 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.
4. G can have multiple minimum spanning trees.

Correct answer: Suppose S ⊂ V 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.

Solution

This statement is true due to the cut property of minimum spanning trees, which asserts that for any cut in the graph, the minimum weight edge crossing the cut must be included in any minimum spanning tree to ensure minimal total weight.

Related GATE Technical questions

• Which one of the following regular expressions correctly represents the language of the finite automaton given below?
• Which one of the following statements is TRUE?
• In a relational data model, which one of the following statements is TRUE?
• Consider the problem of reversing a singly linked list. To take an example, given the linked list below, head -> a -> b -> c -> d -> e -> NULL, the reversed linked list should look like head -> e -> d -> c -> b -> a -> NULL. Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?
• Suppose we are given n keys, m hash table slots, and two simple uniform hash functions h1 and h2. Further suppose our hashing scheme uses h1 for the odd keys and h2 for the even keys. What is the expected number of keys in a slot?
• Which one of the following facilitates transfer of bulk data from hard disk to main memory with the highest throughput?

⚔️ Practice GATE Technical free + battle 1v1 →