Let G(V,E) be an undirected and unweighted graph with 100 vertices. Let d(u,v) denote the number of

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2025 GATE-CS Algorithm paper.

Q: How can I prepare for GATE-CS Algorithm?

To prepare for GATE-CS Algorithm, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2025 question covers Graph Traversals (BFS and DFS) topic.

Q: What is the difficulty level of this question?

This GATE-CS 2025 Algorithm question has a hard difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

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. Let the maximum value of d(u,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?

Accepted Answer

Correct Answer: (C) The height of T is at least 15.Concept — Graph Diameter, Radius, and BFS Tree Height:The diameter of a graph = maximum shortest path distance between any two vertices = max d(u,v) = 30 (given).The eccentricity of vertex v = maxu d(u,v) = maximum distance from v to any other vertex.The radius of a graph = minv eccentricity(v) = minimum eccentricity among all vertices.A BFS tree rooted at vertex s has height = eccentricity of s.Key theorem: For any connected graph: radius ≤ diameter ≤ 2 × radius.This gives: radius ≥ diameter / 2 = 30 / 2 = 15.Interpreting for BFS trees:The BFS tree T is rooted at some vertex s. The height of T = eccentricity of s ≥ radius ≥ 15.Therefore, for any BFS tree T of any graph G with diameter 30, the height of T is at least 15.Why other options are wrong:Option A (exactly 15): The height could be more than 15 if the BFS root is not a center vertex.Option B (exactly 30): The height equals 30 only if the BFS root is a peripheral vertex with eccentricity = diameter. Not guaranteed for every BFS tree.Option D (at least 30): A BFS from the center has height = radius ≥ 15, which could be exactly 15, not necessarily ≥ 30.

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. Let the maximum value of d(u,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?

Master GATE-CS with Our Test Series

More Questions from Graph Traversals (BFS and DFS)

Frequently Asked Questions

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. Let the maximum value of d(u,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?

Master GATE-CS with Our Test Series

More Questions from Graph Traversals (BFS and DFS)

Frequently Asked Questions