Let \(G=(V,E)\) be an undirected unweighted connected graph. The diameter of…
2021
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?
- A.
\(\text{diam}(G_2)\leq\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)\leq 2\; \text{diam}(G)\)
Attempted by 105 students.
Show answer & explanation
Correct answer: A
Key idea: In the new graph, vertices are adjacent exactly when their distance in the original graph is at most 2.
Proof that diameter(G2) ≤ ceil(diameter(G)/2):
Take any two vertices u and v whose shortest-path distance in the original graph is d.
Follow a shortest path of length d from u to v. In the new graph, each step of that path that uses two consecutive original edges can be replaced by a single edge (because vertices at distance 2 are adjacent in the new graph).
Grouping the d original edges into blocks of two gives at most ceil(d/2) edges in the new graph, so the distance between u and v in the new graph is at most ceil(d/2).
Taking the maximum over all pairs u,v (i.e., using d = diameter(G)) yields diameter(G2) ≤ ceil(diameter(G)/2).
Example showing the bound can be tight:
Consider a path graph on n vertices with original diameter n-1. In the new graph, edges connect vertices at distance 1 or 2 along the path, so the new diameter becomes ceil((n-1)/2), achieving the bound.
Conclusion: The correct statement is diameter(G2) ≤ ceil(diameter(G)/2).
A video solution is available for this question — log in and enroll to watch it.