The GATE Grind

GATE 2022 CS – Question 58

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 2 marks · Numerical answer

Let $G(V,E)$ be a directed graph, where $V=\{1,2,3,4,5\}$ is the set of vertices and $E$ is the set of directed edges, as defined by the following adjacency matrix $A$.
$A[i][j]=\begin{cases}1, & 1\le j\le i\le5\\0, & otherwise\end{cases}$
$A[i][j]=1$ indicates a directed edge from node $i$ to node $j$. A directed spanning tree of $G$, rooted at $r\in V$, is defined as a subgraph $T$ of $G$ such that the undirected version of $T$ is a tree, and $T$ contains a directed path from $r$ to every other vertex in $V$. The number of such directed spanning trees rooted at vertex 5 is _____________.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 24

Explanation

$A[i][j]=1$ for $j\le i$: there is an edge $i\to j$ whenever $j\le i$ (including self-loops). From vertex 5 we can reach every smaller vertex.

A directed spanning tree rooted at 5 needs every non-root vertex to have **exactly one incoming tree edge**, coming from a vertex that can reach it.

An edge $u\to v$ exists iff $v\le u$, so vertex $v$ can receive an edge only from a **larger** vertex:
- vertex 4: from 5 only $\Rightarrow$ 1 choice
- vertex 3: from 4 or 5 $\Rightarrow$ 2 choices
- vertex 2: from 3, 4 or 5 $\Rightarrow$ 3 choices
- vertex 1: from 2, 3, 4 or 5 $\Rightarrow$ 4 choices

Any such choice creates no cycle (edges always go from larger to smaller), and every vertex is reachable from 5. Number of trees $=1\cdot2\cdot3\cdot4=\mathbf{24}$.

More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions

All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →