How to determine quickly if these graphs are isomorphic?

Question

I have a collection of 4 graphs, each with 7 vertices [see figure]. I have to determine if the last 3 of them are isomorphic to the first one.

What I have tried so far:

• looking at the degree list of each graph. However, all of them have the same unordered degree list. But from what I understand, that is not conclusive evidence of isomorphism in itself.
• creating an adjacency matrix. The problem is that it's several 7 x 7 matrices, and then I have to find the permutation and transpose and dot product and string representation and canonical values of them...it's a long procedure and I have limited time in the exam.

So I was wondering if there's something I'm missing. Is there a quick way to tell if these are isomorphic?

Which of these graphs are isomorphic to G1?

Answer 1

Your graphs do not all have the same unordered degree sequences. I count

• G1 : $[1, 1, 2, 2, 3, 3, 4]$
• G2 : $[1, 1, 2, 3, 3, 3, 3]$
• G3 : $[1, 1, 2, 3, 3, 3, 3]$
• G4 : $[1, 1, 2, 2, 3, 3, 4]$

There are all sorts of other things you can look at to rule out isomorphism. For example, all the graphs have two vertices of degree one. What is the distance between these two vertices?

Once you think that two graphs probably isomorphic, don't go to a matrix; try to label them. Label the points of one graph 1 through 7, and then try to match the labelling to the second graph. For example, graph $4$ has the same degree sequence as graph $1$. There is a unique vertex of degree $4$, so it has to get the same label in both graphs. Then the vertex of degree $4$ has a unique neighbor of degree $2$, and a unique vertex of degree $3$ so those labels are decided. From there everything should fall into place.

Answer 2

$G_1$ and $G_4$ are isomorphic and $G_2$ and $G_3$ are isomorphic. Each graph has two vertices of degree 1. Look at where their edges join the rest of the graph. If you redraw each graph for maximum symmetry--i.e. reshape the triangle and quadrilateral in each to be an equilateral triangle and square, let's say, and then orient the edges involving the vertices of degree $1$ horizontally or vertically as appropriate, you'll see that $G_1$ and $G_4$ are reflections of each other and ditto for $G_2$ and $G_3$. That makes the isomorphisms easy to spot and this is generally true for graphs of both low order and size.