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.
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?
Solution
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.