Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as: diam(G) = max_{u,v} {the length of shortest paths 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} = 1 if (M_{ij} > 0) or (M^2_{ij} > 0), where P = M^2 N_{ij} = 0 otherwise Which one of the following statements is true? A. diam(G_2) <= ceil(diam(G)/2) B. diam(G_2) >= ceil(diam(G)/2) C. diam(G_2) = ceil(diam(G)/2) D. diam(G_2) = diam(G) - 1
GATE 2021 · Discrete Mathematics · Graph Connectivity · medium
Answer: A. diam(G_2) <= ceil(diam(G)/2)
- Understand G_2 adjacency from the matrix definition: If M_{ij}>0, vertices i and j are direct neighbors. If (M^2)_{ij}>0, there exists k with path i-k-j of length 2 in G. So N_{ij}=1 iff dist_G(i,j) is 1 or 2.
- Prove diam(G_2) <= ceil(diam(G)/2): Take u, v with dist_G(u,v) = d and path u=w_0,w_1,...,w_d=v. In G_2, pair steps: w_0-w_2, w_2-w_4, ... Each pair is a single G_2 edge. Path length in G_2 is ceil(d/2). So dist_{G_2}(u,v) <= ceil(d/2) for all pairs, hence diam(G_2) <= ceil(diam(G)/2).
- Select the correct option: Option A states diam(G_2) <= ceil(diam(G)/2), which is always true. Option C claims equality (not always true). Options B and D are incorrect.