# Checking for graph isomorphism by hand

I'm working through "A First Look at Graph Theory" by Clark & Holton, and in the first exercise, there are problems asking to check whether different graphs are isomorphic to each other. I find it quite difficult to do this for the larger graphs, as the book doesn't seem to point to an algorithm for doing this.

Upon a little searching, I found that there is no polynomial-time algorithm for a general graph, and that the problem has been resolved for only specific cases. But since this has been given as an exercise in the book, I was wondering how people solve it!

Is there some sort of a "visualization" process for doing these isomorphism problems by hand? (For the smaller graphs, I could visualize squishing the edges and moving around the nodes).

Can anyone point out a way to check whether two graphs of say, 8-10 nodes, are isomorphic, by hand, without resorting to any kind of software?

• On the one hand, this is more like a puzzle or riddle, on the other hand human pattern recognition capabilities are often good at spotting broken invariants (e.g. "this graph has two adjacent vertices of degree three and that graph doesn't") Commented Sep 2, 2013 at 17:39
• In general it can be quite difficult. There are tricks you can use; for example, if there is a unique vertex of degree $m$, or a unique vertex of degree $a$ adjacent to a vertex of degree $b$, you can look for the corresponding vertex in the other graph, and then when you find it, delete the vertex and its edges from both graphs, simplifying the problem. But there are cases where none of the tricks apply, and those cases are difficult. Check out the different-looking presentations of the Petersen graph for example.
– MJD
Commented Sep 2, 2013 at 17:42