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

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.

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

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →