UTpaper

Free mock tests & test series

Question 17Asked in UGC NET Computer Science, November 2017 (Paper II & III, Selected Questions)

Let G be an undirected connected graph with distinct edge weight. Let Eₘₐₓ be the edge with maximum weight and Eₘᵢₙ the edge with minimum weight. Which of…

Let G be an undirected connected graph with distinct edge weight. Let Eₘₐₓ be the edge with maximum weight and Eₘᵢₙ the edge with minimum weight. Which of the following statements is false?
  1. AEvery minimum spanning tree of G must contain Eₘᵢₙ
  2. BIf Eₘₐₓ is in minimum spanning tree, then its removal must disconnect G.
  3. CNo minimum spanning tree contains Eₘₐₓ
  4. DG has a unique minimum spanning tree
Show answerHide answer

Correct answer: (C) No minimum spanning tree contains Eₘₐₓ

Explanation

With distinct edge weights the MST is unique and always contains Eₘᵢₙ. Eₘₐₓ can be in the MST (when it is a bridge, its removal disconnects G), so the statement "No minimum spanning tree contains Eₘₐₓ" is false.

From UGC NET Computer Science PYQ, November 2017 (Paper II & III, Selected Questions)

This is question 17 of UGC NET Computer Science PYQ, November 2017 (Paper II & III, Selected Questions). See all questions of this paper with answers, or attempt the paper as a timed online test to get your score and all-India rank.