UGC NET Computer Science December 2019 | Question 57

Question 57

---

A tree has 2n vertices of degree 1, 3n vertices of degree 2. n vertices of degree 3. Determine the number of vertices and edges in tree.

1. 1. 12,11
2. 2. 11,12
3. 3. 10,11
4. 4. 9,10

Explanation

By Handshaking theerem,

Sum of the degree of Vertices = 2 * Number of Edges
∴ 2n*1 + 3n*2 + n*3 = 2*E
∴ E = 11n/2 .........................(1)

As tree having,
Number of Edges = Number of Vertices - 1
E = 2n + 3n - n - 1
E = 6n - 1 .........................(2)

Now, Substituting E = 11n/2 from equation 1
11n/2 = 6n - 1
11n = 12n - 2
n = 2

Now, Substituting n = 2 in equation 2
Number of Edges
E = 6n - 1
= 6n - 1
= 11

As tree having,
Number of Edges = Number of Vertices - 1
Number of Vertices = Number of Edges + 1
So, Vertices = 6n = 12

Number of vertices and edges in tree are 12,11 respectively (2)

Reference 1: Handshaking Theorem
Reference 2: Tree (graph theory)

So, Option 1 (12,11) is the right answer.

Previous	Next
UGC NET CS December 2019 - Question 56	UGC NET CS December 2019 - Question 58