Graphs Problem 2


The node e must match to itself, because it's the only node with degree 8. Similarly, the node a must match to itself because it's the only node with degree 3.

We then have two possible matches for node b: b or d. Once we've made this choice, the matches for d, g, and c are all forced by the need to preserve edge connections.

The ndes f, h, and k are all connected to the rest of the graph in the same way. So we can permute them freely when we do our match. So we have 3! choices for how to match these three nodes.

So in total, there are \(3! \cdot 2 = 12\) isomorphisms from G to itself.


Did you include justification and/or easy-to-understand work showing how you got your answer? This is expected in later math classes and you can lose points for lack of justification even when the question does not explicitly request it. Moreover, if your short answer is wrong, you'll probably get more partial credit if the grader can see how you got it.

When you've made a sequence of choices, you multiply (not add) the number of options for each choice.

Did you subtract 1 from the above answer? Remember that the identity function which just maps each node of G to itself is a perfectly good isomorphism.

Notice that we wrote 3! rather than 6 for most of the problem. For small numbers like this, either method is ok. When the constants are larger (e.g. 7!), it is much better to leave the quantity as a factorial rather than trying to multiply it out. We're trying to figure out if you understand the high-level aspects of the problem. We all have calculators to do the brute-force arithmetic.