UGC-NET Computer Science Data Structures Questions with Explanation

In this Blog we are providing all the UGC-NET Computer Science previous year Questions with explanation:

Q : 5 A certain tree has two vertices of degree 4, one vertex of degree 3 and one vertex of
degree 2. If the other vertices have degree 1, how many vertices are there in the graph ?
(A) 5
(B) n – 3
(C) 20
(D) 11

(UGC-NET Computer Science December 2014)

Answer: (D)

Explanation:

We know that in a tree the total number of edges are always 1 less than total number of vertices.
Also according to handshaking theorem:
Sum of degrees of all the vertices in a graph is equal to twice the number of edges.
So, by applying these two concepts together let total number vertices be 'n'.

   => 2 * 4 + 1 * 3 + 1 * 2 + 1 * ( n - 4 ) = 2*( n - 1 )
   => 8 + 3 + 2 + n - 4 = 2n - 2
   => 13 - 4 + n = 2n - 2
   => n = 11.

Hence correct option is (D).

This question was taken from (UGC-NET Computer Science December 2014 Paper 2).