GATE 2025 CS1 Q.43: solution and answer

Official answer: CSource: Official answer key, GATE 2025 CS1 (IIT Roorkee)

1. Let $\text{diam}(G)={\max }_{u,v}d(u,v)=30$, achieved by some pair of vertices $(x,y)$.

2. For any root $r$, the breadth-first-search tree $T$ rooted at $r$ has height $h(T)={\max }_{v}d(r,v)=\text{ecc}(r)$, the eccentricity of $r$ — because BFS discovers vertices in strictly increasing order of distance from $r$, so the deepest tree level is exactly the farthest distance from $r$.

3. By the triangle inequality on shortest-path distances: $d(x,y)\le d(x,r)+d(r,y)$.

4. Since $r$ is any vertex, both $d(x,r)\le \text{ecc}(r)=h(T)$ and $d(r,y)\le \text{ecc}(r)=h(T)$, so $d(x,y)\le 2h(T)$.

5. Substituting $d(x,y)=30$: $30\le 2h(T)$, hence $h(T)\ge 15$ — and this holds for every root $r$, so for every BFS tree of $G$, and for every graph $G$ satisfying the given diameter condition.

6. Checking the bound is not improvable to equality or to 30 for every case: choosing $r$ to be a 'central' vertex (minimizing eccentricity) can make $h(T)=15$ exactly, which already rules out option (D) ('at least 30') since $15<30$. Choosing $r$ to be a diametral endpoint gives $h(T)=30$, which rules out option (A) ('exactly 15') and option (B) ('exactly 30'), since different roots on the same graph give different heights (15 vs 30).

7. Only option (C), $h(T)\ge 15$, is a statement that holds for every such graph $G$ and every BFS tree $T$ of it.