in Graph Theory edited by
9,710 views
33 votes
33 votes

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$
in Graph Theory edited by
9.7k views

2 Comments

 number of vertices

8
8
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
0
0

2 Answers

39 votes
39 votes
Best answer

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

The correct answer is (D).

edited by
by

2 Comments

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
0
0
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
0
0
2 votes
2 votes
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
Answer:

Related questions