GATE CS 2025 (Forenoon) — Question 43

Discrete MathematicsGraph Theory (Connectivity, Paths, Cycles, Trees)MCQ2 marks · −2/3 if wrongHard

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 \)?
  1. A
    The height of \( T \) is exactly 15.
  2. B
    The height of \( T \) is exactly 30.
  3. C
    The height of \( T \) is at least 15.
  4. D
    The height of \( T \) is at least 30.
Practise the full 2025-FN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAPractise this subject in the exam simulatorTimed, GATE-style tests with analytics that find your weak topics.
Practise more on Graph Theory (Connectivity, Paths, Cycles, Trees)Timed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group