# UGCNET-Dec2014-II: 02

4.6k views

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 ?

1. $5$
2. $n – 3$
3. $20$
4. $11$
in DS
recategorized
1
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

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...

selected
1 vote
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

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

## Related questions

1
2.8k views
Convert the following infix expression into its equivalent post fix expression $(A + B$^$D) / (E – F) + G$ $ABD$^ $+EF – / G+$ $ABD +$^$EF – / G+$ $ABD +$ ^$EF / – G+$ $ABD$^ $+ EF / – G+$
How many PUSH and POP operations will be needed to evaluate the following expression by reverse polish notation in a stack machine $(A ∗ B) + (C ∗ D/E)$? $4$ PUSH and $3$ POP instructions $5$ PUSH and $4$ POP instructions $6$ PUSH and $2$ POP instructions $5$ PUSH and $3$ POP instructions
You have to sort a list $L$, consisting of a sorted list followed by a few ‘random’ elements. Which of the following sorting method would be most suitable for such a task ? Bubble sort Selection sort Quick sort Insertion sort
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: A $2-3$ tree is such that All internal nodes have either $2$ or $3$ children All paths from root to the leaves have the same length. The number of internal nodes of a $2-3$ tree having $9$ leaves could be $4$ $5$ $6$ $7$