GATE CS 2014 Set 1 Q3 — Graphs

A strongly connected component (SCC) of a directed graph $G = (V, E)$ is a maximal subgraph where for every pair of vertices $u, v$, there is a path from $u$ to $v$ and a path from $v$ to $u$.

Let us analyze the options:

• Option B ($G_2$): This is the transpose graph $G^T$, where every edge $(u, v) otin E$ is not used, and instead every edge $(u, v) ext{ in } E$ is reversed to $(v, u) ext{ in } E_2$. If there is a path from $u$ to $v$ in $G$, there is a path from $v$ to $u$ in $G_2$. Thus, mutual reachability is perfectly preserved, meaning $G$ and $G_2$ have the exact same SCCs.
• Option A: The complement graph completely alters the reachability structure.
• Option C: Adding edges for paths of length $\leq 2$ can merge distinct SCCs. For example, in $1 \to 2 \to 3$, $1$ and $3$ are in different SCCs, but adding $(1,3)$ can change the reachability.
• Option D: Removing isolated vertices changes the vertex set $V$, thereby losing the isolated vertices which are themselves SCCs of size 1.

Therefore, the correct option is B.