The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
3.2k 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 Others by Boss (29.7k points)
retagged by | 3.2k 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

+4 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...
by Active (3.8k points)
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
by Loyal (9.2k points)
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
 

by Active (1.8k points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,092 questions
55,239 answers
190,757 comments
85,993 users