Isomorphic 2-graphs

Question

Two graphs

Can we say that these two graphs are isomorphic? I think no because $\deg^-(c) \ne \deg^-(g)$. The solution says they are isomorphic, but I don't understand why. Am I wrong?

Answer 1

Both you and the solution are wrong.

Just saying that $\deg^-(c) \ne \deg^-(g)$ doesn't mean anything, because $c$ doesn't have to be paired with $g$. An isomorphism of these two directed graphs would be a function $$\phi : \{a, b, c, d\} \to \{e, f, g, h\}$$ that preserves directed edges. Checking that $\deg^-(c) \ne \deg^-(g)$ tells you that we cannot have $\phi(c) = g$ in any isomorphism. However, we have $\deg^-(c) = \deg^-(f)$, so we can't immediately rule out that there's an isomorphism $\phi$ with $\phi(c) = f$.

What we can say by looking at indegrees and outdegrees is that any isomorphism must have:

• $\phi(a) = h$, because these are the only vertices with outdegree $2$ and indegree $0$;
• $\phi(b) = g$, because these are the only vertices with outdegree $0$ and indegree $2$;
• either $\phi(c) = e$ and $\phi(d) = f$, or $\phi(c) = f$ and $\phi(d) = e$.

Possibly the solution telling you that the graphs are isomorphic made the mistake of only checking the degrees.

However, once we've figured out the above, we immediately know that there can't be an isomorphism, because there is an edge $(h,g)$ but no edge $(a,b)$.