GATE2025_CS1_Q43

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 ∈ V such that u ≠ 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?

✅ Final Answer:

The correct option is (C) The height of T is at least 15.

🔹 Short Answer:

The height of any BFS tree is the eccentricity of its root. The eccentricity of any vertex is, by definition, greater than or equal to the graph's radius. We use the fundamental inequality relating a graph's diameter and radius: Diameter ≤ 2 × Radius. Given the diameter is 30, we have 30 ≤ 2 × Radius, which implies Radius ≥ 15. Therefore, the height of any BFS tree must be at least 15.

🔸 Long Answer:

This problem requires understanding the properties of Breadth-First-Search (BFS) trees and their relationship with fundamental graph metrics like diameter and radius.

Key Definitions

• BFS Tree (T): A spanning tree generated by a Breadth-First Search starting from a root vertex s. In an unweighted graph, the path from the root s to any other vertex v in the BFS tree is a shortest path in the original graph G.
• Eccentricity e(s): The maximum shortest-path distance from a vertex s to any other vertex in the graph. `e(s) = max{d(s, v) | v ∈ V}`.
• Height of a BFS Tree: The height of a BFS tree rooted at `s` is the maximum distance from `s` to any other node in the tree. This is precisely the eccentricity of the root, `e(s)`.
• Diameter of a Graph: The maximum eccentricity of any vertex in the graph. `Diameter(G) = max{e(v) | v ∈ V}`. The problem gives this as 30.
• Radius of a Graph: The minimum eccentricity of any vertex in the graph. `Radius(G) = min{e(v) | v ∈ V}`.

Step 1: Relate Height of T to Graph Properties

The problem states `T` is *any* BFS tree. This means the root `s` of the tree can be any vertex in the graph. The height of this tree `T` is `e(s)`. Since we need a property that holds for *every* such tree, we need a property that holds for `e(s)` for any chosen `s`.

Step 2: Use the Diameter-Radius Inequality

A fundamental theorem in graph theory states the relationship between the diameter and radius of any connected graph:

Radius(G) ≤ Diameter(G) ≤ 2 × Radius(G)

We are given that `Diameter(G) = 30`. We can use the second part of the inequality to find a lower bound for the radius:

30 ≤ 2 × Radius(G)
Radius(G) ≥ 15

This tells us that the minimum possible eccentricity in this graph is at least 15.

Step 3: Connect Height, Eccentricity, and Radius

The height of any BFS tree `T` (rooted at `s`) is `e(s)`. By definition, the eccentricity of any vertex `s` must be greater than or equal to the minimum eccentricity (the radius).

Height(T) = e(s) ≥ Radius(G)

Combining this with our result from Step 2, we get:

Height(T) ≥ 15

This proves that the height of *any* BFS tree for the given graph `G` must be at least 15.

Step 4: Evaluate Options with a Counterexample

Consider a simple path graph with 31 vertices (and 30 edges). This graph satisfies the conditions.

• Diameter: The distance between `v_0` and `v_30` is 30. This is the maximum shortest path. So, `Diameter = 30`.
• Radius: The most central vertex is `v_15`. Its eccentricity is `e(v_15) = d(v_15, v_0) = 15`. This is the minimum eccentricity. So, `Radius = 15`.
• Case 1: BFS Tree rooted at an endpoint (`v_0`). The height of this tree would be `e(v_0) = d(v_0, v_30) = 30`.
• Case 2: BFS Tree rooted at the center (`v_15`). The height of this tree would be `e(v_15) = 15`.

This single example disproves options (A), (B), and (D), as it shows that the height is not always exactly 15 or 30, and it is not always at least 30. It confirms that the height must be at least 15.

Bibliography:
- Cormen, T. H., et al. (2009). Introduction to Algorithms. MIT Press. (Chapter 22: Elementary Graph Algorithms).
- West, D. B. (2001). Introduction to Graph Theory. Prentice Hall. (Chapter 2: Distances).

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.