UTpaper

Free mock tests & test series

Question 77

From a complete graph by removing maximum ______ edges, we can construct a spanning tree.

  1. Ae − n + 1
  2. Bn − e + 1
  3. Cn + e − 1
  4. De − n − 1
Show answerHide answer

Correct answer: (A) e − n + 1

Explanation

A spanning tree of n vertices keeps exactly n − 1 edges. So from a graph with e edges you remove e − (n − 1) = e − n + 1 edges.

From DSSSB TGT Computer Science Practice Set 4

This is question 77 of DSSSB TGT Computer Science Practice Set 4. 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.