GATE 2022 CS Q.58: solution and answer

Official answer: 24Source: Official answer key, GATE 2022 CS (IIT Kharagpur)

1. Read the matrix: $A[i][j]=1$ exactly when $j\le i$. So there is an edge $i\to j$ for every pair with $j<i$, plus a self-loop at every vertex. A self-loop can never lie in a tree, so ignore the loops.

2. Edges therefore go only from a larger-numbered vertex to a smaller one. Vertex $v$ has incoming edges exactly from the vertices $u$ with $u>v$. Vertex $5$ has no incoming edge at all.

3. A spanning tree on $5$ vertices has exactly $4$ edges. Each vertex $v\ne 5$ must be reached by a directed path from $5$, so the last edge of that path enters $v$. That gives each of the $4$ non-root vertices at least one incoming tree edge. With only $4$ edges in total, each non-root vertex has exactly one incoming tree edge and the root has none.

4. Conversely, pick any one parent $p(v)>v$ for each $v\in \{1,2,3,4\}$. This gives $4$ edges. Starting at any $v$ and repeatedly moving to its parent, the label strictly increases, so no cycle can form and the walk must stop at a vertex with no parent, which is $5$. Reversing the walk gives a directed path from $5$ to $v$. The graph is therefore connected with $4$ edges on $5$ vertices, so its undirected version is a tree. Every such choice is a valid directed spanning tree rooted at $5$.

5. Count the choices of parent. Vertex $4$ may choose from $\{5\}$, so $1$ way. Vertex $3$ from $\{4,5\}$, so $2$ ways. Vertex $2$ from $\{3,4,5\}$, so $3$ ways. Vertex $1$ from $\{2,3,4,5\}$, so $4$ ways.

6. The choices are independent, so the number of trees is $$1\times 2\times 3\times 4=4!=24.$$