GATE IT 2004 | Question: 37

Question

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

• A. $10$
• B. $11$
• C. $18$
• D. $19$

Comments

 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

---

can we do like this : there are 27 edges so total 28 vertices and in that 28 vertices just remove vertices of given degrees so 28-(6+3)=19 ?

Answer 1

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

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

---

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

Answer 2

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