GATE 2023 BT Q.51: solution and answer

Official answer: 15Source: Official answer key, GATE 2023 BT (IIT Kanpur)

1. An unrooted bifurcating (binary) tree for $n$ taxa has $(2n-3)$ branches (edges). For $n=4$ leaves: internal nodes $=n-2=2$, total nodes $=6$, so total edges $=$ nodes $-1=5=2(4)-3$.

2. The number of distinct unrooted binary trees for $n=4$ taxa is $(2n-5)!!=3!!=3$, matching the value given in the question stem (this is a consistency check on the standard formula, not something to be computed from scratch).

3. A root can be inserted at any point along any one of the $2n-3=5$ branches of a given unrooted tree, and each distinct branch placement produces a distinct rooted tree. Hence (number of rooted trees) $=$ (number of unrooted trees) $\times (2n-3)$.

4. Substituting: rooted trees $=3\times 5=15$.

5. Cross-check using the direct closed-form for rooted binary trees, $(2n-3)!!$: for $n=4$, $(2\cdot 4-3)!!=5!!=5\times 3\times 1=15$, consistent with the step-by-step result.