Is there any way, except trial and error, to find an isomorphism for these two graphs?

Question

How can I tell that these graphs are isomorphic and how can I show it?

Answer 1

The way to show that two graphs are isomorphic is to display a concrete isomorphism.

Showing they are not isomorphic is more of an art. Sometimes it is possible to be clever and find some easily discernible property that one of the graphs has and the other one hasn't. But sometimes that isn't possible and the best you can do is argue tediously (and more or less by brute force) why every possible mapping from the vertices of one graph to those of the other is a non-isomorphism.

There's no known efficient algorithm for this that works for arbitrary graphs. In fact, deciding isomorphism of graphs is one of relatively few natural problems that are thought to be NP-intermediate -- which would mean that there is no polynomial algorithm for it, yet it isn't NP-hard.

---

In your concrete case, the graph on the left is the standard drawing of the Petersen graph. That makes it fairly easy to check isomorphism, because the Petersen graph is very symmetric -- for example every 5-cycle is taken into every other 5-cycle by some automorphism. So you can check for isomorphism simply by choosing some 5-cycle on the right, declare that it should match the outer pentagon, and check whether the remaining vertices fit together in the right way for that.

Answer 2

An easy technique for showing is to find the adjacency matrix of these graphs.If the adjacency matrix of one graph can be obtained from other by a suitable permutation of rows/columns then they are isomorphic otherwise not.

The adjacency matrix $A=(a_{ij}):=$

$a_{ij}=1$ if there exists an edge from $v_i$ to $v_j$

   =0 ,otherwise