Question 58

The graph has vertices $V = \{1, 2, 3, 4, 5\}$. A directed edge $(i, j)$ exists if and only if $i \ge j$.

A directed spanning tree rooted at vertex 5 (an arborescence oriented away from the root) satisfies:

1. The root vertex 5 has in-degree 0.
2. Every other vertex $j \in \{1, 2, 3, 4\}$ has in-degree exactly 1 (meaning it chooses exactly one parent $i$).
3. The edge must be directed from parent to child, so $(i, j) \in E$ with $i \ne j$, which requires $i > j$.

Examining the available parent choices for each vertex:

• Vertex 4: Parent $i > 4 \implies i \in \{5\}$ (1 choice).
• Vertex 3: Parent $i > 3 \implies i \in \{4, 5\}$ (2 choices).
• Vertex 2: Parent $i > 2 \implies i \in \{3, 4, 5\}$ (3 choices).
• Vertex 1: Parent $i > 1 \implies i \in \{2, 3, 4, 5\}$ (4 choices).

Because every edge goes strictly from a higher-numbered vertex to a lower-numbered vertex ($i > j$), there can be no directed or undirected cycles among any chosen parent edges. Furthermore, vertex 5 is the unique source with no incoming edges, and every vertex has a path from 5. Therefore, every combination of parent choices produces a valid directed spanning tree rooted at 5.

By the product rule: