July2016 cs Q2 Multiple Choice Questions

Option : C
Explanation :
Spanning trees in complete graph is equal to n^(n-2)(where n is no of sides or regularity in complete graph). So, spanning trees in complete graph K₄ will be 4^{(4 - 2)}. i.e. 4² = 16. Spanning trees in a bipartite graph K_m,n is equal to m^(n-1) * n^(m-1). So, spanning trees in K_2,2 will be 2^(2-1) * 2^(2-1). i.e. 2¹ * 2¹.= 4. So, option (C) is correct.