GATE CS 2022 Set 1 — Question 58

The problem asks for the number of directed spanning trees (arborescences) rooted at vertex 5. A directed spanning tree rooted at $r$ requires that every vertex $v \neq r$ has exactly one incoming edge, and there are no cycles.The adjacency matrix is given by $A[i][j] = 1 \iff 1 \le j \le i \le 5$. This means there is a directed edge $i \to j$ if and only if $i \ge j$. Since self-loops ($i=j$) cannot be part of a spanning tree, valid edges for the tree must satisfy $i > j$. This implies that edges always go from a higher index to a lower index, so the graph is a Directed Acyclic Graph (DAG) (ignoring self-loops). Consequently, any selection of one parent for each node (except the root) will not form a cycle.We need to choose a parent (source node) for each vertex $j \in \{1, 2, 3, 4\}$ such that the parent $i$ satisfies $i > j$ (since the edge is $i \to j$).

• For vertex 4: Possible parents are $i \in \{5\}$ (since $5 > 4$). $\rightarrow$ 1 choice.
• For vertex 3: Possible parents are $i \in \{4, 5\}$ (since $4,5 > 3$). $\rightarrow$ 2 choices.
• For vertex 2: Possible parents are $i \in \{3, 4, 5\}$ (since $3,4,5 > 2$). $\rightarrow$ 3 choices.
• For vertex 1: Possible parents are $i \in \{2, 3, 4, 5\}$ (since $2,3,4,5 > 1$). $\rightarrow$ 4 choices.

The total number of directed spanning trees is the product of the choices for each vertex:$$1 \times 2 \times 3 \times 4 = 24$$Alternatively, using the Matrix Tree Theorem, the Laplacian matrix (in-degree version) for this graph, ordered 1 to 5, is upper triangular with diagonal entries $4, 3, 2, 1, 0$. The number of arborescences rooted at 5 is the cofactor of the $(5,5)$ entry, which is the determinant of the top-left $4 \times 4$ submatrix: $4 \times 3 \times 2 \times 1 = 24$.