Determine whether the following graphs are isomorphic or not

Question

Determine whether the following graphs are isomorphic or not. $\qquad\qquad(a)\text{ Petersen graph}\qquad\qquad\qquad\qquad\qquad\qquad(b)$

First I check degrees of those two graph and unfortunately they are same. Then I tried to find any geometrical shape$(\text{graph invariants})$ which wasn't in other. And I think there is no hexagon shape can possible in figure $1$. Is it enough to said that they are not isomorphic or I have missing something$?$

The graph isomorphism problem is one of few standard problems in computational complexity theory belonging to NP. But are there any special things to check to determine whether two graphs are isomorphic or not. Is there a step by step checklist to check?

Any help will be appreciated. Thanks in advance.
Edited: I update my sketch now it look alike Petersen Graph

Answer 1

As the above labeling shows, the two graphs are isomorphic. Once you have it in your mind that it's possible, it's simple to do. Just pick a 5-cycle, label those vertices A through E, and then the remaining vertex adjacent to A not on that cycle has to be F and so on to the end.

A bunch of years ago, I wrote a proof that there was only one graph up to isomorphism (i.e. the Petersen graph) on ten vertices that was 3-regular and had a diameter of 2. I can post that as well if you are interested.

Answer 2

This is a well-known exercise and appears in at least one text in combinatorial analysis.

To prove isomorphism, it suffices to find a vertex labeling of each graph such that the corresponding adjacency matrices are identical. This furnishes an explicit edge-preserving bijection.

Using the labeling in your figure, and using lexicographical ordering for the Petersen graph as the row/column order for the resulting adjacency matrix, we have $$\begin{array}{c|cccccccccc} & a & b & c & d & e & f & g & h & i & j \\ \hline a & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ b & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ c & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ d & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ e & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ f & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ g & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ h & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ i & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ j & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \end{array}$$

Now all we need to do is identify $\{q, \ldots, z\}$ with $\{a, \ldots, j\}$ so that the resulting adjacency matrix is the same. There clearly is more than one such mapping, so suppose $$\{q, r, w, v\} \to \{a, b, f, e\}.$$ Then since $\{q, r, y, z, w\}$ is a $5$-cycle, it needs to map to a $5$-cycle of the form $\{a, b, ?, ?, f\}$ in the Petersen graph. This forces the choice $y \to c$ and $z \to h$. Similarly, $\{q, v, x, z, w\}$ is another $5$-cycle which must map to $\{a, e, ?, h, f\}$ and the only candidate is $x \to j$. This identifies $7$ of the $10$ vertices and the remaining $3$ are again forced after considering the remaining labels adjacent to $b$ and $e$: $$\{s, t, u\} \to \{g, i, d\}.$$ Thus we have the candidate bijection $$\{q, r, s, t, u, v, w, x, y, z\} \leftrightarrow \{a, b, g, i, d, e, f, j, c, h\}$$ or equivalently $$\{a, b, c, d, e, f, g, h, i, j\} \leftrightarrow \{q, r, y, u, v, w, s, z, t, x\}.$$ Now construct the adjacency matrix for the second graph with this ordering of vertices, and compare the result.