GATE CS 2022 Q48 — Minimum Spanning Trees

A directed spanning tree (or arborescence) rooted at vertex $5$ is a subgraph where every vertex $v \neq 5$ has exactly one incoming edge, and there is a directed path from $5$ to every other vertex.

From the given adjacency matrix $A$, a directed edge exists from $i$ to $j$ if and only if $i \geq j$. Excluding self-loops, a directed edge $i \to j$ exists only when $i > j$. This means edges always go from a higher-numbered vertex to a lower-numbered vertex, which naturally prevents any cycles.

To construct a directed spanning tree rooted at $5$, we must choose exactly one incoming edge (parent) for each vertex $j \in \{1, 2, 3, 4\}$ from the set of vertices $\{i \mid i > j\}$:

• Vertex 4: Parent must be in $\{5\}$ $\implies 1$ choice.
• Vertex 3: Parent can be in $\{4, 5\}$ $\implies 2$ choices.
• Vertex 2: Parent can be in $\{3, 4, 5\}$ $\implies 3$ choices.
• Vertex 1: Parent can be in $\{2, 3, 4, 5\}$ $\implies 4$ choices.

Since these choices are independent and always guarantee a path from the root $5$ to all other vertices, the total number of directed spanning trees is: