# Are two graphs isomorphic if there is a bijective distance-preserving map between them?

Suppose that there exist two connected graphs $G$ and $H$ and a one-to-one function $\varphi$ from the vertex set $V(G)$ onto $V(H)$ such that the distance $\operatorname d_G(u, v) = \operatorname d_H(\varphi(u), \varphi(v))$ for every two vertices $u$ and $v$ of $G$. Prove or disprove: $G$ and $H$ are isomorphic.

Hey guys, I really need some help. I am not sure if the distances in $G$ and $H$ being the same would justify something is isomorphism. I feel it wouldn't tell us if we possibly have cycles, are bipartite etc. I'm having a lot of trouble proving that it is false, if the statement is false.

• Welcome Math.SE! Take the tour to get familiar with this site. Mathematical expressions and equations can be formatted using $LaTeX$ syntax. Please share your thoughts and attempts towards the solution. If you receive useful answers, consider accepting one. – Shailesh Jun 11 '16 at 4:24
• Suppose $\phi: V(G) \rightarrow V(H), v \mapsto v'$ preserves distances. If $u,v \in V(G)$ are adjacent, then their distance is 1, and so $u',v'$ also have distance 1. So $\phi$ preserves adjacency. Similarly, $\phi$ takes nonedges (vertex pairs having distance 2 or more) to nonedges. So $\phi$ is an isomorphism. – Ashwin Ganesan Jun 11 '16 at 16:51

Hint: A bijective function $f$ from $V(G)$ to $V(H)$ is an isomorphism from the graph $G$ to the graph $H$ if for all $u, v \in V(G)$, $u$ is adjacent to $v$ if and only if $f(u)$ is adjacent to $f(v)$ in $H$. Is it possible to rewrite the relation "is adjacent to" in terms of distance?
Vertices $u$ and $v$ of of any $G$ are adjacent if and only if the distance $\operatorname d_G(u,v) = 1$.
The given function $\varphi$ is bijective, and for all $u, v \in V(G)$, $\operatorname d_G(u, v) = 1$ iff $\operatorname d_H(\varphi(u), \varphi(v)) = 1$, or equivalently, $u$ and $v$ are adjacent in $G$ iff $\varphi(u)$ and $\varphi(v)$ are adjacent in $H$. Therefore, $\varphi$ is an isomorphism from $G$ to $H$, so that $G$ and $H$ are isomorphic.