GATE CS 2021 (Forenoon) — Question 46

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

Let \(G = (V, E)\) be an undirected unweighted connected graph. The diameter of \(G\) is defined as
\[ \text{diam}(G) = \max_{u,v \in V} \{\text{the length of shortest path between } u \text{ and } v\} \]
Let \(M\) be the adjacency matrix of \(G\). Define graph \(G_2\) on the same set of vertices with adjacency matrix \(N\), where
\[ N_{ij} = \begin{cases} 1 & \text{if } M_{ij} > 0 \text{ or } P_{ij} > 0, \text{ where } P = M^2 \\ 0 & \text{Otherwise} \end{cases} \]
Which one of the following statements is true?
  1. A
    \(\text{diam}(G_2) \leq \lceil \text{diam}(G)/2 \rceil\)
  2. B
    \(\lceil \text{diam}(G)/2 \rceil < \text{diam}(G_2) < \text{diam}(G)\)
  3. C
    \(\text{diam}(G_2) = \text{diam}(G)\)
  4. D
    \(\text{diam}(G) < \text{diam}(G_2) \leq 2 \text{ diam}(G)\)
Practise the full 2021-FN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Algorithms (CLRS)The standard reference behind most GATE algorithm questions.
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