GATE 2024 CS1 Q.34: solution and answer

Official answer: 16Source: Official answer key, GATE 2024 CS1 (IISc Bengaluru)

1. The graph is the complete graph $K_4$ on the labelled vertices $A,B,C,D$. Each spanning tree has 4 vertices and therefore exactly 3 edges.

2. Cayley's formula: the number of labelled trees on $n$ vertices, which equals the number of spanning trees of $K_n$, is $n^{n-2}$.

3. For $n=4$: $4^{4-2}=4^2=16$.

4. Check by counting. A tree on 4 vertices is either a star or a path. Stars: the centre can be chosen in 4 ways, and the other three vertices attach to it, giving 4 trees. Paths: the 4 vertices can be listed in $4!=24$ orders, and each path appears twice (once read in each direction), giving $24/2=12$ trees. No other tree shape exists on 4 vertices, so the total is $4+12=16$.

5. Second check using edge counts. $K_4$ has 6 edges, so there are $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$ ways to choose 3 edges. Exactly 4 of these choices form a triangle (one for each triple of vertices), and a triangle leaves the fourth vertex isolated, so it is not a tree. Any other 3-edge choice has no cycle and is a spanning tree. That gives $20-4=16$.