Question 51

In a Depth-First Search (DFS) tree $T$ of a connected undirected graph $G$, edges are classified solely into tree edges and back edges (there are no cross edges).

Characterization of the root of $T$:
Because there are no cross edges between distinct subtrees rooted at children of the root, any path between vertices in two different subtrees of the root that does not pass through the root would have to be an edge between those subtrees, which is impossible in an undirected DFS tree. Therefore, removing the root disconnects the subtrees if and only if the root has at least 2 children in $T$. Hence statement B is correct and statement A is false.

Option C: A leaf of $T$ has no descendants in the DFS tree. Removing a leaf cannot disconnect any vertices because all other vertices retain their tree edges among themselves. Thus a leaf cannot be an articulation point in any graph with $|V| \ge 3$. Hence C is false.

Option D: If $u$ is an articulation point, it does not imply that every descendant $y$ is disconnected from every ancestor $x$; some descendants may have back edges going above $u$. It only requires at least one child subtree of $u$ to have no back edge to an ancestor of $u$. Hence D is false in general.

Consequently, only option B is correct.