GATE CS 2022 (Forenoon) — Question 49

AlgorithmsMinimum Spanning Trees (Prim/Kruskal Algorithms)MSQ2 marksMedium

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. A
    The edge with the second smallest weight is always part of any minimum spanning tree of \(G\).
  2. B
    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. C
    Suppose \(S \subseteq V\) be such that \(S \neq \phi\) and \(S \neq V\). Consider the edge with the minimum weight such that one of its vertices is in \(S\) and the other in \(V \setminus S\). Such an edge will always be part of any minimum spanning tree of \(G\).
  4. D
    \(G\) can have multiple minimum spanning trees.
Practise the full 2022-FN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAWhat rank do your marks get?GATE score, likely All-India Rank and qualifying marks for your category.
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