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 uu and vv in VV. Let the maximum value of 𝑑(𝑢,𝑣),𝑢,𝑣∈𝑉𝑑(𝑢, 𝑣), 𝑢, 𝑣 ∈ 𝑉 such that 𝑢≠𝑣𝑢 ≠ 𝑣, be 30. Let TT be any breadth-first-search tree of GG. Which ONE of the given options is CORRECT for every such graph GG ?

  1. A.

    The height of TT is exactly 15.

  2. B.

    The height of TT is exactly 30.

  3. C.

    The height of TT is at least 15.

  4. D.

    The height of TT is at least 30.

Attempted by 259 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…