7
$\begingroup$

enter image description here

I believe that these three graphs are non-isomorphic, because the first graph contains a 6 cycle, which is not present in the other two graphs. The 2nd and 3rd graphs are not isomorphic because they have different numbers of 5 cycles.

enter image description here

$\endgroup$
  • $\begingroup$ Is it possible to align the 2nd image in the center? $\endgroup$ – Sabhrant Jan 27 at 16:20
  • 1
    $\begingroup$ How many $5$-cycles have you counted in the second and third graphs? $\endgroup$ – Blue Jan 27 at 16:31
  • 1
    $\begingroup$ Keep counting in the second graph. $\endgroup$ – Blue Jan 27 at 16:34
  • 1
    $\begingroup$ Right; same number of cycles, so you have to try something else. (This is why the Graph Isomorphism Problem is hard.) Try matching the $5$-cycles from one graph to those of the other. For instance, the inner $5$-cycle of the second graph would be a nice match for one of the "inner" $5$-cycles of the third; go from there. (It would be convenient if you could get the third graph's other "inner" $5$-cycle out of the way ... moving its vertices to the outside, for instance ...) $\endgroup$ – Blue Jan 27 at 16:41
  • 1
    $\begingroup$ The 2nd and 3rd graph are both a ''2D version'' of the dodecahedron actually. $\endgroup$ – Colorblind97 Jan 27 at 16:51
5
$\begingroup$

The inner ring of the third graph consists of two disjoint 5-cycles. If you "drag" one of them to the outside of the (current) outer ring, the isomorphism to the center graph will be clear.

You are correct that the first graph does not have a 5-cycle, so it cannot be isomorphic to the other two.

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