1
$\begingroup$

Given this definition:

If $G_1=(V_1,E_1),G_2=(V_2,E_2)$ are graphs, then $\varphi:V_1\rightarrow V_2$ is a homomorphism iff $\{v_1,v_2\}\in E_1\Rightarrow \{\varphi(v_1),\varphi(v_2)\}\in E_2$

I want to show that if $\varphi$ is a biyective graph homomorphism, then $G_1\cong G_2$.

With this definition of isomorphic graphs:

If $G_1=(V_1,E_1),G_2=(V_2,E_2)$ are graphs, then $G_1\cong G_2$ iff there exist $\phi_1:V_1\rightarrow V_2,\phi_2:E_1\rightarrow E_2$ bijective functions such that: $\{v_1,v_2\}\in E_1\Leftrightarrow\phi_2(\{v_1,v_2\})=\{\phi_1(v_1),\phi_1(v_2)\}$.

I defined $\phi_1=\varphi$ and $\phi_2(\{v_1,v_2\})=\{\varphi(v_1),\varphi(v_2)\}$. And I have already proved it's biyective. But I don't know if I got confused, but I haven't been able to prove the $\Leftarrow$ direction of last implication. Any idea?

$\endgroup$
4
$\begingroup$

If $V_1=V_2=\{1,2\}$ and $E_1=\emptyset$ and $E_2=\{\{1,2\}\}$ and $\phi:V_1\to V_2$ is the identity map, then $\phi$ is a bijective homomorphism, but $G_1$ and $G_2$ are not isomorphic.

$\endgroup$
  • $\begingroup$ Wow, then the book has a mistake. Are there any conditions for it to be true? $\endgroup$ – David Molano Mar 7 '15 at 20:24
  • $\begingroup$ What book is that? $\endgroup$ – bof Mar 7 '15 at 20:46
  • $\begingroup$ Johnsonbaugh. First interesting proof in the chapter and ends up being false D:. $\endgroup$ – David Molano Mar 7 '15 at 22:43
  • $\begingroup$ Maybe you misread the exercise, or maybe there is a typo? Could you quote it verbatim? $\endgroup$ – bof Mar 7 '15 at 23:24
  • $\begingroup$ The only thing I think I forgot to say is that those have to be simple graphs. It says: "A homomorphism from a graph $G_1$ to a graph $G_2$ is a function $f$ from the vertex set of $G_1$ to the vertex set of $G_2$ with the property that if $v$ and $w$ are adjacent in $G_1$, then $f(v)$ and $f(w)$ are adjacent in $G_2$." $\endgroup$ – David Molano Mar 7 '15 at 23:41

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.