Let $G = (V, E)$ be an undirected unweighted connected graph. The $\textit{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?

In an unweighted graph $G$:

• $M_{ij} > 0$ indicates that there is a path of length $1$ between vertex $i$ and vertex $j$.

• $P_{ij} = (M^2)_{ij} > 0$ indicates that there is a walk of length $2$ between vertex $i$ and vertex $j$.

Thus, an edge $(i, j)$ exists in graph $G_2$ if and only if the shortest path distance between $i$ and $j$ in $G$ satisfies $1 \le d_G(i, j) \le 2$.

For any two vertices $u, v \in V$, let $d_G(u, v) = k$ be the shortest path distance between them in $G$. Along this shortest path of length $k$, we can jump up to $2$ edges per step in $G_2$. Therefore, the shortest path distance between $u$ and $v$ in $G_2$ satisfies:

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

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