Question

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 \neq 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 \)?

• A. The height of \( T \) is exactly 15.
• B. The height of \( T \) is exactly 30.
• C. The height of \( T \) is at least 15.
• D. The height of \( T \) is at least 30.

Hint:

In a BFS tree, the height corresponds to the maximum number of edges from the root to any leaf node. The maximum shortest path length in the graph gives us a lower bound for the height of the BFS tree.

Answer 1

The Correct Option is C

Let's analyze the problem step by step:

Step 1: Understanding the problem
We are given an undirected graph \( G \) with 100 vertices.
The maximum shortest path distance between any two vertices in the graph is 30, i.e., for some pair of vertices \( u \) and \( v \), \( d(u, v) = 30 \).

Step 2: BFS and the height of the tree
Breadth-First Search (BFS) explores all vertices in layers based on their distance from the starting vertex (root).
The height of the tree is determined by the maximum depth (distance from the root) of any vertex in the BFS tree.

Step 3: Maximum Distance in BFS Tree
The maximum distance between any two vertices is 30, and this distance corresponds to the longest path between any two vertices in the graph.
In a BFS tree, the height is the maximum distance from the root vertex to any other vertex. The longest path between any two vertices in the graph implies that there is at least one vertex in the BFS tree that is 30 edges away from the root.

Step 4: Conclusion
Since the maximum shortest path in the graph is 30, the height of the BFS tree is at least 15. This is because the longest path of 30 edges is split across the tree, and the BFS tree must span across this distance. It is not possible for the height to be less than 15 because any path of length 30 would require at least half of it (15 levels) to reach the maximum distance.

Thus, the correct answer is (C) The height of \( T \) is at least 15.