9,244 views

What is the number of vertices in an undirected connected graph with $27$ edges, $6$ vertices of degree $2, 3$ vertices of degree $4$ and remaining of degree $3$?

1. $10$
2. $11$
3. $18$
4. $19$

number of vertices

let x be the no. of vertices to be calculated.

According to the Handshaking lemma ,

The sum of degree of all the vertices = 2* |E|

6 * 2 + 3 * 4 + (x-9) * 3 = 2 * 27

→ 12 + 12 + 3x – 27 = 54

→ 24 + 3x = 54 + 27

→ 3x = 54 + 27 – 24

→ 3x = 57

→ x = 19

So , the no. of vertices is (D) 19

sum of degree of all the vertices $= 2 *$ number of edges.

$2\times 6 + 4\times 3 + 3\times x = 27\times 2$

$x=10.$

Number of vertices $= 6 + 3 +x = 19.$

by

so given total edges 27

6 vertices having degree 2 means 12 edges

3 vertices having degree 4 means 12 edges so total 24 edges

27- 24 gives 3 edges remaining  there is possibility of only one vertex

ans is 6+3+1=10 ? i think this is also possible correct this if it is wrong
Whenever you add an edge in graph it increases the total digree by 2.thats why sum of digrees=2*no. Of edges.

Edge is connecting two vertices at a time
Let x = Total no. of vertices
By Handshaking Lemma,
6 * 2 + 3 * 4 + (x - 9) * 3 = 27 * 2
24 + (x - 9) * 3 = 54
x = 19

1
5,289 views