Prove or disprove: Let $G$ and $H$ be two connected graphs of order $n$ (order is the number of vertices of a graph), where $V(G)=\{v_1,v_2\ldots,v_n\}$. If there exists a one-to-one correspondence $\phi: V(G)\to V(H)$ such that $d_G(v_i,v_{i+1})=d_H(\phi(v_i),\phi(v_{i+1}))$ for all $i$ $(1\leq i \leq n-1)$, then $G\simeq H$, that is, $G$ and $H$ are isomorphic.
Some definitions:
- The degree of a vertex $v$ in a graph $G$ is the number of edges incident with $v$ and is denoted by $\mbox{deg}_G(v)$.
- The distance between vertices $u$ and $v$ in a graph $G$ is the smallest length of any $u-v$ path in $G$ and is denoted by $d_G(u,v)$.
My guess is that this statement is false and as counterexample consider the graphs $G_1$ and $G_2$ below
$\hskip 1.5in$ 
I'll use the following result:
- If $G$ and $H$ are isomorphic graphs, then the degrees of the vertices of $G$ are the same as the degrees of the vertices of $H$.
So, consider the function $\phi: V(G_1)\to V(G_2)$ defined by $\phi(v_i)=v_i$ for all $1\leq i\leq n$, i.e., the identity function.
Certainly $\phi$ is one-to-one and $d_G(v_i,v_{i+1})=d_H(\phi(v_i),\phi(v_{i+1}))$ for all $i$ $(1\leq i \leq n-1)$. On the other hand, $G_1\not\simeq G_2$ since $\mbox{deg}_{G_1}(v_4)=1$ and $\mbox{deg}_{G_2}(v_4)=2$.
Is this counterexample correct? If not, why?
Best Answer
Yes your counter example works. The two graphs are not isomorphic but they satisfy all the desired conditions.