Question

Let $G=(V,E)$ be an undirected unweighted connected graph. The diameter of $G$ is defined as: \[ \text{diam}(G) = \max_{u,v \in V} \{\text{length of the 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?

• A. $\text{diam}(G_2) \le \lceil \text{diam}(G)/2 \rceil$
• B. $\lceil \text{diam}(G)/2 \rceil < \text{diam}(G_2) < \text{diam}(G)$
• C. $\text{diam}(G_2) = \text{diam}(G)$
• D. $\text{diam}(G) < \text{diam}(G_2) \le 2\,\text{diam}(G)$

Hint:

Adding edges corresponding to paths of length $2$ effectively halves the longest shortest paths in a graph.

Answer 1

The Correct Option is A

Step 1: Interpretation of $G_2$.
The matrix $M^2$ captures the number of walks of length exactly $2$ between pairs of vertices. Hence, in $G_2$, an edge exists between two vertices if their distance in $G$ is either $1$ or $2$. Thus, $G_2$ effectively "shortcuts" paths of length $2$ into single edges.

Step 2: Effect on shortest paths.
Any shortest path of length $k$ in $G$ can be traversed in $G_2$ by covering two edges of $G$ at a time. Therefore, the distance between any two vertices in $G_2$ is at most $\lceil k/2 \rceil$.

Step 3: Relation between diameters.
Since the diameter is the maximum shortest-path length over all vertex pairs, we obtain \[ \text{diam}(G_2) \le \left\lceil \frac{\text{diam}(G)}{2} \right\rceil. \]

Step 4: Conclusion.
Hence, option (A) correctly describes the relationship between the diameters of $G$ and $G_2$.