Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as:
diam(G) = max‌limitsu,x∈V {the length of shortest path between u and v}
Let M be the adjacency matrix of G.
Define graph G₂ on the same set of vertices with adjacency matrix N, where
Nij={
1‌ if ‌Mij>0‌ or ‌Pij>0 ‌ where ‌P=M2
0 ‌ otherwise ‌
.
Which one of the following statements is true?

Question

1‌ if ‌Mij>0‌ or ‌Pij>0	‌ where ‌P=M2
0	‌ otherwise ‌

.
Which one of the following statements is true?

Examsnet · Accepted Answer

Correct Answer is : diam(G2) ≤ ⌊diam(G)∕2⌋

GATE Computer Science (CS) 2021 Shift 1 Solved Paper