How to tell whether two graphs are isomorphic?

In general, it's a hard problem

There's no known efficient algorithm that is guaranteed to tell you whether two graphs are isomorphic. Of course, we could try all possible permutations of the vertices, but this will take a very long time. We know heuristics: good things to try which will work in many cases, but will sometimes give us an inconclusive answer.

But we can solve it by hand for small examples

In practice, when the number of vertices is not too large, we can often check for isomorphism without too much work. We do this by picking out distinguishing features of the vertices in each graph. Then we have fewer bijections between the vertex sets to check to see if the graphs are isomorphic.

One of the simplest distinguishing features of a vertex is its degree: the number of edges out of that vertex. For the example in the question, we notice that:

• Vertices $\{A, B, E, F, H, I\}$ of the first graph have degree $3$, and vertices $\{C,D,G\}$ have degree $4$.
• Vertices $\{4, 5, 6, 7, 8, 9\}$ of the second graph have degree $3$, and vertices $\{1,2,3\}$ have degree $4$.

So we have reduced our search space significantly from $9! = 362,880$ to $6! \cdot 3! = 4,320$ graph isomorphisms: that's the number of bijections between the vertex sets that send $\{A,B,E,F,H,I\}$ to $\{4,5,6,7,8,9\}$ and $\{C,D,G\}$ to $\{1,2,3\}$. (And if the numbers of vertices of each degree didn't match up, we'd know very quickly that there's no graph isomorphism.)

We can further distinguish between the vertices of each degree. For instance, in the first graph, $\{A,E,I\}$ are vertices of degree $3$ that are adjacent to vertices of degree $4$; $\{B,F,H\}$, on the other hand, are vertices of degree $3$ whose neighbors all have degree $3$. This narrows the search space even more.

If we start filling in a partial graph isomorphism, pieces fall into place as we go. For example, we could try seeing if there's a graph isomorphism that maps $C$ to $1$. Then $A$ (a neighbor of $C$ which has degree $3$) must be mapped to $4$ or $6$ (neighbors of $1$ which have degree $3$). If $A$ is mapped to $4$, then $D$ (a neighbor of $A$ and $C$) must map to $3$ (a neighbor of $1$ and $4$), and pretty soon the entire isomorphism is there.

To make this work, we will need to do some casework, and might need to backtrack, but usually you should not expect to have many branches to try. Highly symmetric graphs are harder to tackle this way, and in fact they are the places where computer algorithms stumble, too.

Another example of looking at degrees

Here is another example of graphs we might analyze by looking at degrees of vertices.

If we write down the degrees of all vertices in each graph, in ascending order, we get:

• $2, 2, 2, 3, 3, 4, 5, 5$ for the graph on the left;
• $2, 2, 3, 3, 3, 4, 4, 5$ for the two other graphs.

This tells us that the first graph is not isomorphic to the other two, because the degree sequences don't match up.

Importantly, it does not tell us that the two other graphs are isomorphic, even though they have the same degree sequence. In fact, they are not isomorphic either: in the middle graph, the unique vertex of degree $5$ is adjacent to a vertex of degree $2$, and in the graph on the right, the unique vertex of degree $5$ is only adjacent to vertices of degree $3$ or $4$.

Graph invariants

A more general approach to graph isomorphism is to look for graph invariants: properties of one graph that may or may not be true for another. (The degree sequence of a graph is one graph invariant, but there are many others.) This is usually a quick way to prove that two graphs are not isomorphic, but will not tell us much if they are.

For example:

• Is the number of vertices and edges in one graph the same as in the other?
• If one graph is planar, is the other graph also planar?
• If one graph is bipartite, is the other graph also bipartite?
• If one graph contains two cycles of length $3$, does the other graph also contain two cycles of length $3$?

More elaborate invariants exist. For example, we can compute the Tutte polynomial of both graphs: if we get different values, then the graphs are not isomorphic. Unfortunately, if two graphs have the same Tutte polynomial, that does not guarantee that they are isomorphic.

Links

• See the Wikipedia article on graph isomorphism for more details.
• Nauty is a computer program which can be used to test if two graphs are isomorphic by finding a canonical labeling of each graph.

One method which is useful for graphs with small number of vertices is to try to visualize a continuous deformation of one graph which changes it into another graph. For example, for the given graphs, if in the second graph, vertex $3$ is "pulled" sufficiently up to the other side of the edge $\{1, 2\}$ and the vertex $9$ is also pulled up on the other side of the edge $\{7, 8\}$, then the resulting graph is the same as the first graph. A bijection between the two vertex sets is then easily formed.