UTpaper

Free mock tests & test series

Question 15Asked in UGC NET Computer Science, June 2016 (Paper II & III, Selected Questions)

The number of different spanning trees in complete graph, K₄ and bipartite graph, K₂,₂ have _________ and _________ respectively.

  1. A14, 14
  2. B16, 14
  3. C16, 4
  4. D14, 4
Show answerHide answer

Correct answer: (C) 16, 4

Explanation

The number of spanning trees in a complete graph with n vertices = nⁿ⁻² = 4⁴⁻² = 16. A complete bipartite graph Kₘ,ₙ has mⁿ⁻¹ × nᵐ⁻¹ spanning trees = 2¹ × 2¹ = 4.

From UGC NET Computer Science PYQ, June 2016 (Paper II & III, Selected Questions)

This is question 15 of UGC NET Computer Science PYQ, June 2016 (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.