0
$\begingroup$

I'm supposed to find two graphs $G$ and $H$ such that there exist morphisms $G\mapsto H$ and $H\mapsto G$, but $G$ and $H$ are not isomorphic.

I just can't understand how that's even possible.. you'd need both graphs to have the same number of vertices and edges so that morphism maps direction can be genuine functions in either direction (right?), and then the graphs would have to be connected the same so that the morphism maps compose with the endpoint maps of the graphs correctly (right?)

In case that doesn't make sense if this isn't the usual definition of morphisms (my lecturer commented that graph theory in particular seems to have many definitions for the same thing), We have that a morphism between graphs $(G,E,\varepsilon)$ and $(G',E',\varepsilon' )$ is a pair of maps $\phi:V\mapsto V'$ and $\psi : E\mapsto E'$ such that $\varepsilon' \circ \psi = \phi^* \circ \varepsilon.$

$\endgroup$
1
$\begingroup$

Hint:

  • Isomorphism is required to be a bijection, however an ordinary graph homomorphism does not have such constraints.
  • Take $K_{1,1}$ and $K_{2,2}$ (the full bipartite graphs).
  • It is easy to construct a mapping $K_{1,1} \to K_{2,2}$.
  • Can you construct a mapping from $K_{2,2}$ to $K_{1,1}$ that preserves the adjacency relation? (You will have to map multiple vertices into a single one.)

I hope this helps $\ddot\smile$

$\endgroup$

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.