Let \(𝐺(𝑉, 𝐸)\) be an undirected and unweighted graph with 100 vertices.…
GATE · 2025 · CS · Set 1 · Computer Science & IT
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 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.
Attempted by 245 students.
Show answer
Correct answer: C
The worked solution is available to enrolled students.
Video solution available to enrolled students.
Explore the full course: Iocl Engineers Officers Grade A Paper 2