0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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") $\endgroup$ Commented Sep 2, 2013 at 17:39
  • 2
    $\begingroup$ 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. $\endgroup$
    – MJD
    Commented Sep 2, 2013 at 17:42

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .