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 ?

  1. A.

    5

  2. B.

    n – 3

  3. C.

    20

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

Explore the full course: Mppsc Assistant Professor