Number of isomorphisms between two graphs

2.3k Views Asked by At

enter image description here

I'm studying for an exam in graph theory, and this question came up. The question is: how many isomorphisms exist between these two graphs. I know that, as they are isomorphic, this is the same as answering how many isomorphisms there are from the graph to itself.

I think the answer is $6$ or $3$, but I'm struggling to prove/show why this is correct/incorrect. Is there an easy way to see what the correct answer is, without explicitly writing down all the possible bijections?

Thanks

edit: I've included the graphs as a link now.

1

There are 1 best solutions below

0
On

Consider an arbitrary isomorphism, $G'$, of $G$, and its corresponding bijection, $f$. We must preserve the adjacency and non adjacency of $G$.

Let us start (without loss of generalization) with $a$, which we will map to an arbitrary vertex of degree 2 in $G'$. We have 4 choices possible. Notice that no matter which vertex you pick, its neighbors will be $v$, a vertex of degree 2, and $w$, a vertex of degree 3. Since we must preserve the adjacency and non adjacency of $G$, it follows that the vertex of degree 3 must be labelled $b$, and the vertex of degree 2 must be labelled $f$.

It should be very easy to complete the proof after this point, since our first choice forces every other vertex to be a certain label.

I hope this helped!