# How to determine quickly if these graphs are isomorphic?

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?

• For the graphs in the figure, looking at degree of vertices is a good way to tell if which graphs aren't isomorphic. Creating an explicit isomorphism isn't too bad in the remaining case(s). – Alvin Jin Nov 28 '15 at 21:04

• 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]$
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.
$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.