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?
You can try using some general heuristics about the properties that are preserved by graph isomorphisms. For example, graph isomorphisms preserve degree, so that already limits where certain nodes might be sent. Graph isomorphisms preserve the existence of cycles, the number of connected components, etc. You can use these results as guides to whittle down the number of possible isomorphisms to a small number you can check by hand.