What is the number of vertices in an undirected connected graph with 27 edges,…
2004
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
Attempted by 263 students.
Show answer & explanation
Correct answer: D
Solution:
Use the handshaking lemma: the sum of degrees of all vertices equals twice the number of edges.
Total edges = 27, so sum of degrees = 2 × 27 = 54.
Known contributions: six vertices of degree 2 contribute 6×2 = 12; three vertices of degree 4 contribute 3×4 = 12. Together these give 24.
Let r be the number of remaining vertices of degree 3. Their contribution is 3r. So total degree sum is 24 + 3r.
Set 24 + 3r = 54. Solve: 3r = 30, so r = 10.
Total vertices = 6 + 3 + r = 9 + 10 = 19.
Answer: 19 vertices.
A video solution is available for this question — log in and enroll to watch it.