GATE CSE 2021 Set 1 Q46: Diameter of the graph joining vertices within distance two

Let $G = (V, E)$ be an undirected unweighted connected graph. The diameter of $G$ is defined as:

$\operatorname{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?

Try it: multiple choice: exactly one correct option

Wrong answer costs 2/3 mark in GATE.

Show answer and explanation

Answer: A (official GATE 2021 final answer key)

Concept used: $(M^2)_{ij} > 0$ means a walk of length 2 from $i$ to $j$ , so $G_2$ joins all pairs at distance 1 or 2 in $G$ .

First step: A shortest path of length $d$ in $G$ can be covered two edges at a time in $G_2$ : how many $G_2$ edges does it need?

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

Source: official GATE 2021 Set 1 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key