# Graphs Problem 2

### Solution

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.

### Comments

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.