GATE 2025 CS (CS1) – Question 43
Let $G(V,E)$ be an undirected and unweighted graph with 100 vertices. Let $d(u,v)$ denote the number of edges in a shortest path between vertices $u$ and $v$ in $V$. Let the maximum value of $d(u,v)$, $u,v \in V$ such that $u \ne v$, be 30. Let $T$ be any breadth-first-search tree of $G$. Which ONE of the given options is CORRECT for every such graph $G$?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) The height of $T$ is at least 15.
Explanation
Let $d_{max}$ be the largest shortest-path distance (here 30). Take a BFS tree rooted at some vertex $r$. Its height equals the **eccentricity** of $r$, the largest distance from $r$ to any vertex.
- The eccentricity of any vertex is at most the diameter, 30.
- The eccentricity of any vertex is at least the **radius**, and always $\text{radius}\ge\frac{\text{diameter}}{2}$. (If $u,v$ are at distance 30, then for any $r$, $d(r,u)+d(r,v)\ge30$, so one of them is at least 15.)
So the height of the BFS tree is at least $15$, but it can be anywhere from 15 to 30 depending on the graph and the root. The only statement true for every such graph is "at least 15": option (C).
More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions
- GATE 2025 CS (CS1) Q64
- GATE 2025 CS (CS2) Q29
- GATE 2025 CS (CS2) Q37
- GATE 2025 CS (CS2) Q59
- GATE 2024 CS (CS1) Q45
- GATE 2024 CS (CS1) Q60
All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →