Is it necessary to perform a cycle check in isomorphism?

Question

While checking Isomorphism between two graphs, is it enough if I just check the degrees of all vertices and if the degrees of all vertices connected to every given vertex are identical in both graphs?

Is it also necessary to check for identical cycles in both graphs?

For example: https://i.stack.imgur.com/ptXaF.jpg

In the above image, it is possible to have a mapping between vertices of both graphs as both graphs have 2 vertices of degree 2 and 4 vertices of degree 3. Furthermore, every vertex of degree 3 is connected to 2 vertices of degree 3 and one vertex of degree 2 in both Graphs. Finally, the vertices with degree 2 are both connected to two vertices of degree 3.

But Graph 1 does not have a 3-vertex cycle like Graph 2. So are they isomorphic?

Answer 1

None of the "simple" degree and/or cycle conditions like you mention are sufficient for graph isomorphism, or otherwise checking if two graphs are isomorphic would be algorithmically easier than it really is.

However, they are necessary, so if they are not satisfied, the graphs cannot be isomorphic. As in your example - one graph has triangles, the other doesn't.