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\)?
Answer
(C)
Explanation
In a BFS tree rooted at \(r\), every vertex sits at depth equal to its shortest-path distance from \(r\), so the height of \(T\) is the largest distance from \(r\) to any vertex.
Take \(u, v\) with \(d(u, v) = 30\). For any root \(r\), \(30 = d(u, v) \le d(u, r) + d(r, v)\), so \(r\) is at distance at least 15 from \(u\) or from \(v\). Hence the height is always at least 15 (and never more than 30).
Both extremes occur: take a path of 31 vertices and attach the other 69 vertices to its middle vertex. BFS from the middle vertex gives height 15, and BFS from an end of the path gives height 30. So A, B and D can fail, and only C holds for every such graph.
Answer: C