GATE CS 2021 (Afternoon) — Question 11

AlgorithmsMinimum Spanning Trees (Prim/Kruskal Algorithms)MCQ1 mark · −1/3 if wrongMedium

Let \(G\) be a connected undirected weighted graph. Consider the following two statements. \(S_1\) : There exists a minimum weight edge in \(G\) which is present in every minimum spanning tree of \(G\). \(S_2\) : If every edge in \(G\) has distinct weight, then \(G\) has a unique minimum spanning tree. Which one of the following options is correct?
  1. A
    Both \(S_1\) and \(S_2\) are true.
  2. B
    \(S_1\) is true and \(S_2\) is false.
  3. C
    \(S_1\) is false and \(S_2\) is true.
  4. D
    Both \(S_1\) and \(S_2\) are false.
Practise the full 2021-AN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Algorithms (CLRS)The standard reference behind most GATE algorithm questions.
Practise more on Minimum Spanning Trees (Prim/Kruskal Algorithms)Timed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group