2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Shailesh Jun 11 '16 at 4:24
  • 1
    $\begingroup$ 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. $\endgroup$ – Ashwin Ganesan Jun 11 '16 at 16:51
2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Thank you for the hint, it helped a lot! $\endgroup$ – Jason Jun 12 '16 at 3:30
  • $\begingroup$ @Jason I you have received a helpful answer, you can accept it (if you choose to do so) by clicking on the check mark next to the answer. $\endgroup$ – bof Jun 25 '16 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.