GATE CS 2021 Set 1 Q41 — Trees

Let us analyze the properties of a Depth First Search (DFS) tree $T$ for a connected undirected graph $G$:

• Option A & B: In a DFS tree of an undirected graph, there are only tree edges and back-edges (no cross-edges). The root of $T$ is an articulation point if and only if it has $2$ or more children in $T$. If it has only $1$ child, removing the root leaves the single subtree connected. Thus, Option B is correct and Option A is incorrect.
• Option C: A leaf node in $T$ has no descendants. Removing a leaf node cannot disconnect any other vertices because the remaining vertices stay connected via the rest of the spanning tree $T$. Thus, a leaf can never be an articulation point. Option C is incorrect.
• Option D: Suppose $u$ is an articulation point because it has a child subtree $C_1$ with no back-edges to any ancestor of $u$. If $u$ has another child subtree $C_2$ that does have a back-edge to an ancestor $x$ of $u$, then for any descendant $y ext{ in } C_2$, there exists a path from $x$ to $y$ (via the back-edge) that completely bypasses $u$. Thus, not all paths from $x$ to $y$ must pass through $u$. Option D is incorrect.