A certain tree has two vertices of degree 4, one vertex of degree 3 and one…
2014
A certain tree has two vertices of degree 4, one vertex of degree 3 and one vertex of degree 2. If the other vertices have degree 1, how many vertices are there in the graph ?
- A.
5
- B.
n – 3
- C.
20
- D.
11
Attempted by 112 students.
Show answer & explanation
Correct answer: D
Key idea: use the handshaking lemma for a tree: the sum of degrees equals twice the number of edges, i.e. 2(n-1).
Sum the given non-leaf degrees: two vertices of degree 4 give 8, one of degree 3 gives 3, and one of degree 2 gives 2, so total = 13.
Let r be the number of degree-1 vertices (leaves). Then total number of vertices is n = 4 + r, and the total degree sum is 13 + r.
Apply the handshaking lemma: 13 + r = 2(n - 1) = 2(4 + r - 1) = 6 + 2r.
Solve for r: 13 + r = 6 + 2r ⇒ r = 7. Therefore n = 4 + 7 = 11.
Answer: 11 vertices.
A video solution is available for this question — log in and enroll to watch it.