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

Answer 1

The correct option is D 19

Sum of degree of all vertices = 2e (using Handshaking lemma)

So, 6 × 2 + 3 × 4 + x × 3 = 2 × 27
12 + 12 + 3x = 54
3x = 54 - 24
$x=\frac{30}{3}$

x = 10

So, total number of vertices

$\Rightarrow x+6+3=10+6+3=19$