Let \(πΊ(π, πΈ)\) be an undirected and unweighted graph with 100 vertices.β¦
2025
LetΒ \(πΊ(π, πΈ)\) be an undirected and unweighted graph with 100 vertices. LetΒ \(π(π’, π£)\) denote the number of edges in a shortest path between verticesΒ \(u\) andΒ \(v\) in \(V\). Let the maximum value ofΒ \(π(π’, π£), π’, π£ β π\) such that \(π’ β π£\), be 30. LetΒ \(T\) be any breadthfirst-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.
Attempted by 151 students.
Show answer & explanation
Correct answer: C
Given: the graph has diameter 30, i.e. the maximum shortest-path distance between any two vertices is 30.
Key facts:
The height of a breadth-first-search (BFS) tree rooted at a vertex equals that vertex's eccentricity, i.e. the maximum distance from that root to any vertex.
The radius of the graph is the minimum eccentricity over all vertices.
A standard inequality relates diameter and radius: diameter β€ 2 Γ radius. Rearranged, this gives radius β₯ ceil(diameter/2).
Apply these facts with diameter = 30:
radius β₯ ceil(30/2) = 15.
Every vertex's eccentricity is at least the radius, so every vertex's eccentricity β₯ 15.
Therefore, the height of any BFS tree (being the eccentricity of its root) is at least 15.
Why the other exact/strong statements fail:
The height need not be exactly 15: if the BFS root is chosen at a central vertex the height can be 15, but other roots can give larger heights.
The height need not be exactly 30 or at least 30: if the root is chosen near the center the height can be 15, so 30 is not a guaranteed lower bound.
Conclusion: The only statement that is always true for every BFS tree of every graph with diameter 30 is that the height is at least 15.
A video solution is available for this question β log in and enroll to watch it.