0
$\begingroup$

I have the following graphs and I am trying to identify if they are isomorphic or not.

enter image description here

The solutions that I have indicate they are isomorphic, with the following bijection:

enter image description here

However, it appears that the graph on the right has more 3-cycles than the graph on the left. The graph on the left also contains an obvious 4-cycle, where the graph on the right does not. The degrees of all the vertices are the same.

It's my understanding that two graphs cannot be isomorphic if they have a differing number of x-cycles. What am I missing here?

$\endgroup$
1
$\begingroup$

Think of this as pushing the vertices $f,b,d$ inside of the triangle $a,e,c$. There are plenty of four cycles in the second graph as well one is $a \rightarrow b \rightarrow d \rightarrow e \rightarrow a$

$\endgroup$
  • $\begingroup$ Actually with the labelling the isomorphism is the identity map. So each cycle in the first graph IS a cycle in the second graph without a change in the vertex labels. $\endgroup$ – baharampuri May 18 '15 at 5:45
0
$\begingroup$

The reason is simple, if you look closely you'll see no verticies lines has been broken nor any verticies been removed, hence they ahve just moved around and are therefore the same, isomorphic.

$\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.