Graphs Problem 3


With isomorphism problems, you need to try two approaches in parallel. On the one hand, try to find a way to match up nodes in a way that preserves the edge connections. On the other hand, look for local features that don't match (which would prove they aren't isomorphic).

Have you checked the obvious features

If any of these don't match, you're done: they aren't isomorphic. If they do match, you need to keep working.

Write the node degree on each node. It will help you think about which nodes from the other graph are potential matches to it.

Look in each graph for copies of special graphs such as cycles, wheels, complete graphs. If the left graph contains (say) a 5 wheel then any isomorphic graph must also contain one.