# Thread: Are any of the following graphs isomorphic?

1. ## Are any of the following graphs isomorphic?

Hi there,

I am trying to do this question from my textbook. I couldn't reproduce the diagrams so I've just taken a photo of it.

As far as I know there's no simple way of checking, it's generally done by intuition and inspection. I know there are ways of showing that two graphs are NOT isomorphic (eg different degree sequence, different number of edges etc.) but I can't apply those here.

All 3 graphs have 10 vertices, 15 edges, and every vertex has degree 3. Thus they all have (3, 3, 3, 3, 3, 3, 3, 3, 3, 3) - I know that generally having the same degree sequence doesn't prove isomorphism, but does it in this case? I have a suspicion that if two graphs have degree sequences of (k, k, k, ...., k) then they are isomorphic, is that right?

Another approach I took was to find the adjacency matrices of each graph. This took some doing. My book says that if 2 graphs have similar adjacency matrices then they are isomorphic. However, I have 3 10x10 matrices all with 0s and 1s as their entries. They all have determinant 0, trace 0. Is this sufficient to show they are similar?

It is my belief that all 3 pairs of these graphs are isomorphic, but the second part of the question asks me to find an isomorphism - how on earth would I do that?

Many thanks,
R

2. It looks to me as though in the left graph (the Petersen graph) every cycle has length 5. But the middle graph has a 6-cycle (the outer circle), and the right graph has some 4-cycles (but no 6-cycles that I can see). So my guess is that all three graphs are nonisomorphic. But I don't know a quick or convincing way to prove that.

3. Originally Posted by Opalg
It looks to me as though in the left graph (the Petersen graph) every cycle has length 5. But the middle graph has a 6-cycle (the outer circle), and the right graph has some 4-cycles (but no 6-cycles that I can see). So my guess is that all three graphs are nonisomorphic. But I don't know a quick or convincing way to prove that.
In fact, there is a 6 cycle in Petersen graph - see the attachment and check 1-1'-3'3-4-5.

The attachment should show you that 1 and 2 are isomorphic.

They are not isomorphic to the 3rd one, since it contains 4-cycle and Petersen's graph does not. (Every vertex of Petersen graph is "equivalent". To find a cycle, you would have to find two paths of length 2 starting in the same vertex and ending in the same vertex. If you try all 3 neighbors of some vertex, you see, that no two of them have a common neighbor.)

EDIT:
http://images.google.com/images?q=petersen+graph leads to more planar drawings of Petersen graph, this one is containing two of your graphs: