Suppose that we are given two graphs on a relatively small number of vertices. Here's an example:
Are these two graphs isomorphic? (That is: is there a bijection $f$ from $\{A,B,\dots,I\}$, the vertex set of the first graph, to $\{1,2,\dots,9\}$, the vertex set of the second graph, such that $vw$ is an edge of the first graph if and only if $f(v)f(w)$ is an edge of the second graph?)
- If not, how can we tell?
- If so, how can we tell—and how can we find an isomorphism?
This question comes up a lot, usually asking about specific examples of two graphs which may or may not be isomorphic. Sometimes, the fiendish teacher of graph theory will even give three or more graphs and ask "Which of these are isomorphic?"
I'm asking this question so that we can provide a single canonical answer to questions of this type which would be worth linking to when specific instances of this question come up. So all improvements and/or suggestions are welcome!
Best Answer
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:
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:
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:
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