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 vertices of degree 3?
A. 10
B. 11
C. 18
D. 19
GATE 2004 · Discrete Mathematics · Graph Connectivity · medium
Answer: 19
Apply Handshaking Lemma: 2 * 27 = 54. Setting up: 6*2 + 3*4 + r*3 = 54, where r is the number of remaining (degree-3) vertices.
Solve for r and compute total vertices: 12 + 12 + 3r = 54 => 3r = 30 => r = 10. Total vertices = 6 + 3 + 10 = 19.