# A bijection of a connected graph that preserves 2-distances but is not an automorphism

Does there exist a connected graph $$G$$ and a bijection $$\varphi: V(G) \to V(G)$$ with the property that $$d(u, v) = 2 \Leftrightarrow d(\varphi(u), \varphi(v)) = 2$$, but $$\varphi$$ is not an automorphism? I haven't been able to come up with a counterexample, but I haven't been able to get a hold of a proof either.

Let $$G$$ be a line with three segments, i.e., $$V=\{a,b,c,d\}$$ and $$E=\{\{a,b\},\{b,c\},\{c,d\}\}.$$ Let $$\varphi=\{(a,a),(b,d),(c,c),(d,b)\}.$$ This is not an automorphism because it maps a vertex of degree $$2$$ to a vertex of degree $$1,$$ but it preserves the relationship "has distance $$2$$ to" between vertices.
• @Lieven I was actually thinking of just swapping two vertices that are distance 2 apart, rather than rotating three - but both fall under your paradigm. I think you need to extend condition 1 to "all vertices of that colour are at distance exactly 2 from one another AND not distance 2 to vertices of any other colour". e.g. consider the graph $1-2-3-4-5$. Then swapping $3$ and $5$ is not a valid example, because of the distances to $1$.