A certain tree has two vertices of degree 4, one vertex of degree 3, and one…

Concept

The handshaking lemma states that the sum of all vertex degrees equals twice the number of edges. A tree with n vertices has exactly n − 1 edges, so its degree sum is 2(n − 1); the edge count is therefore determined by n and need not be supplied separately.

Application

1. Let r be the number of degree-1 vertices. The four specified non-leaf vertices and these r leaves give n = 4 + r.

2. The specified non-leaf degrees contribute 2 × 4 + 3 + 2 = 13, and the leaves contribute r, so the total degree sum is 13 + r.

3. Because the graph is a tree, it has n − 1 edges. Apply the handshaking lemma: 13 + r = 2(n − 1) = 2(4 + r − 1).

4. Simplify: 13 + r = 6 + 2r, hence r = 7.

5. Therefore n = 4 + r = 4 + 7 = 11 vertices.

Cross-check

For any tree, the number of leaves is 2 plus the sum of d − 2 over vertices of degree d ≥ 3. Here this gives 2 + 2(4 − 2) + (3 − 2) = 7 leaves; adding the four non-leaf vertices again gives 11.

Result: the graph has 11 vertices.