Nice Isomorphic Question and way of finding Quickly?

Question

I see a question about Isomorphic Graph. the question is:

The first line graph is not isomorphic with which one in the second line?

How we can find isomorphic graph without knowing some geometry map (like rotate or ...)?

Answer 1

I think the easiest method would be to recognize the given graph as a pentagon with two non-adjacent vertices connected (since a $5$-pointed star is isomorphic to a simple $5$-cycle; a pentagon). The connection isn't a single edge, but an edge that's been turned into two edges by putting a point in the middle.

You can identify that three of the four graphs can be constructed in this same manner.

Alternatively, the $4$th graph in the second row is the only one with a $6$-cycle, but that's a little harder for me to see, personally.

Answer 2

All the graphs have two vertices of order three and four of order two. The last graph has the two order three vertices connected by an edge, while the rest do not. It is therefore not isomorphic to any other. I have not shown that the rest are isomorphic, but this is enough for the question.

Answer 3

Current algorithms do not solve graph isomorphism efficiently in the worst case. The best result is an algorithm due to Babai, Kantor and Luks that runs in $2^{O(\sqrt{n \log n})}$ time [Babai, Kantor and Luks, Computational complexity and the classification of finite simple groups, 1983].

If you don't care about the worst case, there are heuristic algorithms that work for all but an exponentially small proportion of graphs in linear time. See [Practical graph isomorphism II, McKay and Piperno, 2013].