Skip to content
GATEiit

GATE CSE 2025 Session 1 Q43: BFS tree height when the graph diameter is 30

Question

Let G(V,E)G(V, E) be an undirected and unweighted graph with 100 vertices. Let d(u,v)d(u, v) denote the number of edges in a shortest path between vertices uu and vv in VV. Let the maximum value of d(u,v)d(u, v), u,v∈Vu, v \in V such that u≠vu \ne v, 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?

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 2/3 mark in GATE.
Show answer and explanation

Answer: C (official GATE 2025 final answer key)

Concept used: A BFS tree from root rr has height equal to the eccentricity of rr, which lies between half the diameter and the diameter.

First step: For the two vertices u,vu, v at distance 30, the triangle inequality gives d(r,u)+d(r,v)≥30d(r, u) + d(r, v) \ge 30, so one of them is at depth at least 15.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2025 Session 1 CS question paper and final answer key, organised by IIT Roorkee. Question paper · Answer key

More Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2025 Session 1 questions →