Let $G=(V, E)$ be an undirected unweighted connected graph. The diameter of $G$ is defined as:
$$\text{diam}(G)=\displaystyle \max_{u,v\in V} \{\text{the length of shortest path between $u$ 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}=\left\{\begin{array} {lll} 1 &\text{if}\; M_{ij}>0 \text{ or } P_{ij}>0, \text{ where }P=M^2\\0 &\text{otherwise} \end{array}\right.$$
Which one of the following statements is true?
- $\text{diam}(G_2)\leq\lceil \text{diam}(G)/2\rceil$
- $\lceil \text{diam}(G)/2\rceil<\text{diam}(G_2)< \text{diam}(G)$
- $\text{diam}(G_2) = \text{diam}(G)$
- $\text{diam}(G)< \text{diam}(G_2)\leq 2\; \text{diam}(G)$