GATE CS 2024 Set 1 Q24 — Graphs: Connectivity, Matching, Colouring

According to Cayley's Formula, the number of spanning trees in a complete labeled graph $K_n$ with $n$ vertices is given by:

For the given complete graph with $4$ labeled vertices ($\text{A, B, C, D}$), we have $n = 4$. Substituting this value into the formula:

Alternative Verification:

We can classify the spanning trees of $K_4$ by their structural isomorphism types:

1. Star Graphs ($S_4$): One central vertex of degree 3 connected to three leaf vertices.
   • The central vertex can be chosen in $\binom{4}{1} = 4$ ways.
   • This gives $4$ spanning trees.
2. Path Graphs ($P_4$): A simple path of length 3 containing all 4 vertices.
   • The number of ways to arrange 4 distinct vertices in a line is $4! = 24$.
   • Since a path is identical when read forwards or backwards, we divide by 2: $\frac{24}{2} = 12$ ways.
   • This gives $12$ spanning trees.

Total number of spanning trees = $4 + 12 = 16$.