GATE CS 2021 Set 1 — Question 46

To find the relationship between the diameter of the original graph $G$ and the modified graph $G_2$, we analyze the definition of the adjacency matrix $N$ of $G_2$.

1. Understanding the Construction of $G_2$

Let $d_G(u, v)$ denote the shortest path distance between vertices $u$ and $v$ in $G$, and $d_{G_2}(u, v)$ denote the shortest path distance in $G_2$.The adjacency matrix $N$ of $G_2$ is defined as:N_{ij} = 1 \iff M_{ij} > 0 \quad \text{or} \quad (M^2)_{ij} > 0 \quad (\text{for } i $\neq$ j)

• $M_{ij} > 0$ means there is a path of length $1$ between $i$ and $j$ in $G$.
• $(M^2)_{ij} > 0$ means there is a path of length $2$ between $i$ and $j$ in $G$.

Thus, an edge exists between $u$ and $v$ in $G_2$ (i.e., $d_{G_2}(u, v) = 1$) if and only if the shortest path distance between them in $G$ satisfies:$$1 \le d_G(u, v) \le 2$$

2. Relationship Between Distances in $G$ and $G_2$

Let $u$ and $v$ be any two vertices in $V$. Suppose the shortest path between $u$ and $v$ in $G$ has length $L = d_G(u, v)$.
We can write this path as a sequence of vertices:$$u = x_0, x_1, x_2, \dots, x_L = v$$where $d_G(x_i, x_{i+1}) = 1$ for all $0 \le i < L$.We can construct a shorter path in $G_2$ by skipping every alternate vertex:

• Since $d_G(x_0, x_2) = 2$, there is an edge between $x_0$ and $x_2$ in $G_2$.
• Since $d_G(x_2, x_4) = 2$, there is an edge between $x_2$ and $x_4$ in $G_2$.
• In general, for any even step, $d_G(x_{2k}, x_{2k+2}) = 2 \implies d_{G_2}(x_{2k}, x_{2k+2}) = 1$.

By grouping the edges of the path in $G$ into pairs of length $2$ (with possibly one remaining edge of length $1$ at the end if $L$ is odd), we can reach $v$ from $u$ in $G_2$ in at most $\lceil L/2 \rceil$ steps. Thus, the distance in $G_2$ satisfies:$$d_{G_2}(u, v) \le \lceil d_G(u, v) / 2 \rceil$$

3. Relating the Diameters

The diameter of a graph is the maximum of the shortest path distances between any pair of vertices. Let $u^*, v^*$ be the pair of vertices in $G_2$ that realizes the diameter of $G_2$:$\text{diam}(G_2) = d_{G_2}(u^*, v^*)$Using the inequality derived above:$\text{diam}(G_2) = d_{G_2}(u^*, v^*) \le \lceil d_G(u^*, v^*) / 2 \rceil$Since $d_G(u^*, v^*)$ is at most the diameter of $G$ ($\text{diam}(G)$), we have:$\text{diam}(G_2) \le \lceil \text{diam}(G) / 2 \rceil$This inequality holds strictly or with equality for all connected undirected graphs. Therefore, Option A is the correct statement.