Graphs Problem 2

Hints

You may find this problem easier to understand if you draw a second copy of the graph with different node labels, e.g. A through H in place of a through h. Let's call this second copy G'.

An isomorphism maps the nodes of G one-to-one onto the nodes of G'. If a pair of nodes is connected by an edge in G, then the corresponding pair of nodes must be connected by an edge in G'. Similarly, if there is no edge between two nodes in G, they must be mapped onto a pair of nodes in G' without an edge.

Think of building an isomorphism using a series of choices. Decide where to map one node. This choice will limit your options when you look at where to map other nodes.

Start the process by identifying important constraints. Are there some nodes of G that have only one possible corresponding node in G'? For example, perhaps the node is the only node with a particular degree. Does the graph split naturally into two pieces that can be considered more-or-less independently?