UGC NET CSE | December 2014 | Part 2 | Question: 02

Question

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$ 

Comments

Let number of vertices of degree 1 be k.

No of vertices = k + 2 + 1 + 1 = k +4  (we have two vertices of degree 4, one vertex of degree 3 and one vertex of degree 2)

No of edges = No of vertices -1 // As it is a tree

                   = k + 3

Applying  handshaking lemma

2 * 4 + 1 * 3 + 1 *2 + 1* k = 2 ( no edges ) = 2 * ( k +3)

=> 13 + k = 2k + 6

=> k = 7

So number of vertices = k +4 = 11

Answer 1

Answer is D

there are two vertices with degree 4, one vertex with degree 3 , one vertex with degree 2 and let x vertex with degree 1......therefore total number of vertices is (x+4)

Now by handshaking lemma we know..... sum of degrees of all vertices=2e ( where e is number of edges)

therefore 8+3+2+x=2e

              2e-x=13............(i)

Now in a tree number of edges is one less than number of vertices..

Therefore      e=x+4-1

                  e-x=3................(ii)

Solving (i) and (ii) we get........e=10 and x=7

Now total number of vertices is x+4 which is 11...

Answer 2

Let number of vertices of degree 1 be k.

No of vertices = k + 2 + 1 + 1 = k +4  (we have two vertices of degree 4, one vertex of degree 3 and one vertex of degree 2)

No of edges = No of vertices -1 // As it is a tree

                   = k + 3

Applying  handshaking lemma

2 * 4 + 1 * 3 + 1 *2 + 1* k = 2 ( no edges ) = 2 * ( k +3)

=> 13 + k = 2k + 6

=> k = 7

So number of vertices = k +4 = 11

Answer 3

in the given question is asking about no. of  vertices in the tree as we know that  

e(edge)=n(no. of vertice)-1

using the handshake theorem sum of degree = 2|e|

2*4+1*3+1*2+(n-(2+1+1))*1=2|n-1|

 { (n-(2+1+1))*1 ------> remaining other vertices }

8+3+2+n-4=2n-2

8+3+2+2-4=2n-n

11=n

 

two vertices of degree 4, one vertex of 3 and one vertex of degree ‘2’. If all other vertices have degree 1