search
Log In
3 votes
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
4.6k views
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

3 Answers

5 votes
 
Best answer
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...

selected by
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
0 votes

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
 

Answer:

Related questions

2 votes
2 answers
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+$
asked Jul 21, 2016 in DS makhdoom ghaya 2.8k views
3 votes
4 answers
2
3k views
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
asked Jul 18, 2016 in DS makhdoom ghaya 3k views
3 votes
3 answers
3
2.8k views
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
asked Jul 21, 2016 in Algorithms makhdoom ghaya 2.8k views
18 votes
4 answers
4
3.2k views
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$
asked Sep 13, 2014 in DS Kathleen 3.2k views
...