Let G=(V,E) be an undirected, unweighted, connected graph. Its diameter is the…

Concept

In a graph square, vertices at original distance one or two become adjacent. Thus one edge in the squared graph represents a walk of at most two edges in the original graph. Self-loops, if retained, never shorten a path between distinct vertices.

Application

1. The diagonal entry Pii counts length-two closed walks and may be positive. Setting Nii=0 removes those loops; even retaining them would not alter any distance between distinct vertices.

2. Choose any vertices u and v and write d=dist_G(u,v). Along a shortest u-v path in G, group consecutive edges into blocks of two, with one final single-edge block when d is odd.

3. Each block becomes one edge of G2, so dist_G2(u,v) ≤ ⌈d/2⌉.

4. Conversely, every non-loop edge of G2 represents a walk of length one or two in G. A G2 path of k edges therefore expands to a G walk of length at most 2k, giving d ≤ 2 dist_G2(u,v), hence dist_G2(u,v) ≥ ⌈d/2⌉.

5. Combining the bounds gives dist_G2(u,v)=⌈dist_G(u,v)/2⌉. Maximizing over all vertex pairs yields diam(G2)=⌈diam(G)/2⌉.

Cross-check and contrast

For a path with L edges, G2 permits jumps of one or two original edges, so its endpoints are exactly ⌈L/2⌉ edges apart. This attains the bound.

• The relation diam(G2) ≤ ⌈diam(G)/2⌉ follows immediately from the equality.

• A strict lower bound above ⌈diam(G)/2⌉ contradicts the equality.

• Equality with diam(G) occurs only in small special cases and is not a universal identity.

• Adding distance-two edges cannot make the diameter larger.

Hence the true statement is diam(G2) ≤ ⌈diam(G)/2⌉.