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
Best Answer
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.