# Symmetries of a graph

Determine the number of symmetries in the following graph:

What are the general things you should do when finding such symmetries? Usually I would label all of them from $1...n$ and note their valency mentally

I am still not clear on how you would progress though. I thought that I could permute the point 1 to any of the other points with valancy three, but I have been told you can't, although I am still not sure why.

Could someone explain this?

So taking the fact that the point 1 has to be fixed, it was then said there were $3!$ permutations of the outer points (the points branching from point 1 (2,5,8)) and for each of those outer points, $2!$ permutations of the points attached to them.(i.e for point 2, there would be $2!$ permutations of 3 and 4)

Why is it that, for example, points 3 and 4 can only be rearranged and that 3 could not be permuted to point 10 for example. They both have the same valency, I am just a bit unclear on why you can't.

Many thanks.

-

Looking at the valencies is not enough. A rearrangement of the labels is only a symmetry if labels that were connected by an edge before are connected after, and labels that were unconnected before are still unconnected after. This will preserve the valencies, but not every mapping that preserves valencies is a symmetry.

For example, consider this graph:

There are two symmetries here: you can have $ABCDE\to ABCDE$, or you can flip the whole thing over, $ABCDE\to EDCBA$. $B$ and $D$ are in symmetrical positions, and there is a symmetry taking $B\to D$ and $D\to B$. But there is no symmetry that takes $C\to D$ even though both have valence 2. $C$ is in the middle of the line, and $D$ is not. This should correspond to the idea of "symmetry" that you had before you took this class.

In your original graph, the point 3 can go to 10, but if it does, point 2, to which it is attached, must go to 8, which is attached to 10. Then point 4, which is also attached to 2, must go to 9.

So once you've decided that 2 goes to 8, you know that 3 and 4, which were attached to 2, must go to 9 and 10, which are attached to 8. You get to choose whether $3\to9, 4\to 10$, or $3\to 10, 4\to 9$, but that's the only further choice you get about 3 and 4.

As you noted, 1 must go to 1. (We'll deal with why that is later on.) Then 2, 5, and 8 must go to 2, 5, and 8, but each of those could go to any of the others, so there are 6 choices about how to arrange them. Let's say that we have $(2,5,8)\to(8,2,5)$ just as an example. Then 3 and 4, which were attached to 2 before, must be attached to 8 after, so they must go to 9 and 10. You can choose whether \begin{align}& 3\to9, & 4\to 10,\\ \text{or} & 3\to 10,& 4\to 9,\end{align} as in the previous paragraph. Then similarly you can choose whether \begin{align}& 6\to3, & 7\to 4,\\ \text{or} & 6\to 4,& 7\to 3,\end{align} and you can choose whether \begin{align}& 9\to10, & 6\to 11,\\ \text{or} & 9\to 11,& 6\to 10.\end{align}

That means that after you choose one of six ways to map $2,5,8$, you get three independent choices about how to flip the forks at the ends of the arms. Each choice has two possible ways to go, so the total number of choices is $3!\cdot2!\cdot2!\cdot2! = 24$, and that's the answer.

Now you said you are not sure why we must have $1\to 1$. Let's try $1\to 5$ and see what happens. Since 1 is attached to 258, and 5 is attached to 167 we must have each of 258 going to something in 167. But 258 all have valence 3 while 6 and 7 have valence only 1, so there is nothing that can go properly to 6 or to 7. So $1\to 5$ will never work. And 2 and 8 look just like 5, so $1\to 2$ and $1\to 8$ will fail for essentially the same reason.

-
 You meant $3! \cdot 2 \cdot 2 \cdot 2 = 48$, right? – Marek Jan 17 at 16:32 Thank you so much for taking the time to write out such a clear and well written answer. – CAF Jan 17 at 16:38 You're welcome. I was afraid it was too long. – MJD Jan 17 at 16:39