GATE CS 2021 Set 1 Q36 — Graphs: Connectivity, Matching, Colouring

The adjacency matrix $N$ of the graph $G_2$ is defined such that $N_{ij} = 1$ if $M_{ij} > 0$ or $P_{ij} > 0$ (where $P = M^2$).

• $M_{ij} > 0$ means there is a path of length $1$ between vertices $i$ and $j$ in $G$.
• $P_{ij} > 0$ means there is a path of length $2$ between vertices $i$ and $j$ in $G$.

Thus, an edge exists between $i$ and $j$ in $G_2$ if and only if the shortest path distance between them in $G$ is at most $2$.

Let $d_G(u, v)$ and $d_{G_2}(u, v)$ denote the shortest path distances between any two vertices $u$ and $v$ in $G$ and $G_2$, respectively. If $d_G(u, v) = k$, we can traverse this path in $G_2$ by taking leaps of distance $2$ at each step. This requires at most $\lceil k/2 \rceil$ steps. Therefore:

Taking the maximum over all pairs $u, v \in V$ to find the diameter:

Hence, $\text{diam}(G_2) \le \lceil \text{diam}(G)/2 \rceil$.