Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Determine the number of symmetries in the following graph:

enter image description here

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.

share|cite|improve this question
up vote 8 down vote accepted

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:

line graph with 5 vertices

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 agree with 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.

original example graph

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\atop 4\to 10$, or $3\to 10\atop 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\to6, & 10\to 7,\\ \text{ or } & 9\to 7,& 10\to 6.\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! = 48$, 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.

share|cite|improve this answer
Thank you so much for taking the time to write out such a clear and well written answer. – CAF Jan 17 '13 at 16:38
You're welcome. I was afraid it was too long. – MJD Jan 17 '13 at 16:39

Consider using the orbit-stabilizer lemma, which states that: if $G \le Sym(V)$ is a permutation group acting on $V$ and $v \in V$, then $|G|=|v^G|~|G_v|$. Here $v^G$ is the orbit of $v$ under the action of $G$, and the stabilizer $G_v$ is the set of elements in $G$ that fix $v$.

Thus, to find the size of automorphism group $G$ of the tree above, pick a vertex $v$, say $v=1$, and find the number of vertices that 1 can be mapped to by an automorphism of the tree and find the number of automorphisms that fix vertex 1. In this case, vertex 1 is the center of this tree and hence must be fixed by every automorphism (automorphisms preserve distances, and every longest path in the tree has vertex 1 as its midpoint). Thus $|v^G|=1$. An automorphism fixing a vertex must permutes its neighbors amongst themselves, hence every automorphism must induce a permutation of $\{2,5,8\}$. Furthermore, all $3!$ permutations of these neighbors are possible. Observe that the number of automorphisms that fix the vertex 1 and each of its neighbors 2, 5, and 8, is $2^3=8$. Hence, the total number of automorphisms of this graph is the product $3!~ 2^3=48$.

share|cite|improve this answer

There are various meanings that can be given to "symmetries of the following graph." One can interpret it as meaning automorphisms of the graph but one can also think about the symmetries of the "drawing" of the graph in the plane. In this case the graph is a tree so there is a drawing in the plane without crossings of this graph, as drawn in the figure. However, for drawings one often has in mind that the diagram is metric rather than combinatorial. Consider for example, the complete graph on 4 vertices. This graph has 24 symmetries or automorphisms. It also has two "natural" metrical drawings in the plane. One is a square with its diagonals, which has 8 symmetries. Note that this drawing is not a plane graph since the diagonals cross at a point which is not a vertex of the graph. One can also use the drawing consisting of an equilateral triangle, and its centroid joined to the vertices. This is a plane drawing but it has only 6 symmetries.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.