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 V such that 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? 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.

Official answer: C) The height of T is at least 15.. Explanation: The diameter of the graph G is given as: diam(G) = u, v V d(u, v) = 30 Let r be the root vertex chosen to start the Breadth-First Search (BFS). In a BFS tree T rooted at r, the depth (level) of any vertex v corresponds to the shortest path distance from r to v, i.e., d(r, v). The height of the BFS tree T is the maximum distance from the root r to any vertex in the graph: h(T) = v V d(r, v) By the triangle inequality for shortest path distances in an undirected graph, for any pair of vertices u, v V: d(u, v) d(u, r) + d(r, v) Since d(u, r) h(T) and d(r, v) h(T), we have: d(u, v) 2 h(T) Taking the maximum over all pairs (u, v): diam(G) 2 h(T) 30 2 h(T) h(T) 15 Depending on the choice of the root r, the height h(T) can range from 30/2 = 15 (if r is a central vertex) up to 30 (if r is an eccentric peripheral vertex). Thus, the height of T is always at least 15. Hence, option C is correct.

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.

Algorithms · Graph Traversals

Official IIT answer key · IIT Guwahati · Audited Aug 2026

Take topic test

GATE CSE 2025 Set 1 Q43 · MCQ · 2 marks

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 \neq 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$ ?

Select an option to check

Key concept

Graph Traversals

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Graph Traversals

GATE tests Graph Traversals (BFS and DFS) through deep theoretical properties rather than simple code tracing. Key emphases include edge classification (tree, back, forward, cross edges), timestamp intervals via the Parenthesis Theorem, DAG topological orderings, and structural invariants like the BFS level difference inequality and tree height versus graph diameter. Recent papers heavily favor MSQs and multi-property conceptual deductions over simple single-answer lookups.

Full Graph Traversals guide →

More on Graph Traversals

All 16 questions on Graph Traversals →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Algorithms · Graph Traversals

Official IIT answer key · IIT Guwahati · Audited Aug 2026

Take topic test

GATE CSE 2025 Set 1 Q43 · MCQ · 2 marks

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 \neq 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$ ?

Select an option to check

Key concept

Graph Traversals

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Graph Traversals

Full Graph Traversals guide →

More on Graph Traversals

All 16 questions on Graph Traversals →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2025 Set 1

More on Graph Traversals

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2025 Set 1

More on Graph Traversals

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2025 Set 1

More on Graph Traversals

Share this solution

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2025 Set 1

More on Graph Traversals

Share this solution