Growth of graph powers

NEW

Problem: Reconstructed conjecture: for every finite simple loopless undirected connected $d$-regular graph $G$ with $\operatorname{diam}(G)\ge 3$, where $G^3$ joins pairs of vertices whose $G$-distance is at most $3$, one has

This matches Pokrovskiy’s notation and the surrounding statement about regular connected graph powers.

Result: The conjecture is false. Here is an explicit counterexample.

Let $G$ have vertex set

where

Define edges as follows.

• $v$ is adjacent to every vertex of $A$.
• $A$ induces $K_{10}$ with the three disjoint edges

deleted.

• $b$ is adjacent to $a_1,\dots,a_6$.
• $\{b\}\cup C$ induces $K_5$.
• $X$ induces $K_8$.
• Between $C$ and $X$, each $c_i$ is adjacent to all of $X$ except the following two vertices:

• There are no other edges.

Every vertex has degree $10$:

vertices $a_1,\dots,a_6$ have $8+1+1=10$, vertices $a_7,\dots,a_{10}$ have $9+1=10$, each $c_i$ has $4+6=10$, and each $x_j$ has $7+3=10$. Thus $G$ is $10$-regular on $24$ vertices, so

The graph is connected and has diameter $4$. Indeed $v$ has distance exactly $4$ from each $x_j$, via a path

with $c_i\sim x_j$, and no shorter path exists because $v$ only meets $A$, no vertex of $A$ meets $C\cup X$, and $b$ does not meet $X$. All other pairs are at distance at most $4$.

The pairs at distance exactly $4$ are precisely

There are $5\cdot 8=40$ such pairs. Since $\operatorname{diam}(G)=4$, $G^3$ is the complete graph on $24$ vertices with exactly these $40$ pairs missing. Therefore

But

so

Thus the reconstructed conjecture is disproved.

Citation: No known literature citation is used for this counterexample.