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