3.4k 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 | 3.4k 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

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...
by Active (3.8k points)
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
by Boss (11.5k points)

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

by Active (1.8k points)