The GATE Grind

GATE 2025 CS (CS1) – Question 43

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Multiple choice

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$?

  1. The height of $T$ is exactly 15.
  2. The height of $T$ is exactly 30.
  3. The height of $T$ is at least 15.
  4. The height of $T$ is at least 30.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) The height of $T$ is at least 15.

Explanation

The BFS tree height equals the eccentricity of its root, which lies between the radius and the diameter (30). Since radius ≥ diameter/2, the height is at least 15, but need not be exactly 15 or 30.