Determine no. elements in $ \operatorname{Aut}(H)$ where $H$ is the 6 point/5line graph in the shape of H

Question

Determine the amount of automorphisms in the group $\operatorname{Aut}(H)$ where $H$ is the graph with 6 points and five lines in the shape of a capital 'H'. Here is what it should look like, I labeled the points:

Now I can clearly see that rotation through the line $12$ and rotation through a vertical axis through the middle will be automorphisms. These can be described by permutation in $S_6$ in the following way: $$\sigma_1 = (1\ 3)(4\ 6)$$ and $$\sigma_2 = (1\ 4)(2\ 5)(3\ 6)$$ then we also have point reflection through the middle which is given by: $$\sigma_3 = \sigma_1 \sigma_2 = (1\ 6)(2\ 5)(3\ 4)$$ Is this all the symmetries of $H$? I am confused because I do not think the answer should be this simple. If I for instance have the permutation $(2\ 5)$ then will the points $2$ and $1$ still be connected meaning the line piece from $2$ to $1$ will be diagonal implying $(2\ 5)$ is not an automorphism or am I missing something? Thanks in advance

Answer 1

First of all, what's a graph homomorphism? In my definition, it's a map $f: G\to H$ (by which I mean it sends vertices to vertices and edges to edges) such that, if $(a,b)$ is an edge in $G$, then $(f(a),f(b))$ is an edge in $H$.

First of all, you should convince yourself that it's enough to work out where the vertices go: if $f: H\to H$ is an automorphism and you know what $f(a)$ is for all vertices $a$ in $H$, you know where all the edges are. (Why is this?) Having done this, you can just specify automorphisms as permutations in $S_6$ like you've been doing.

Secondly, to answer you rather obliquely: the two reflections and one point rotation you've found are automorphisms; but are there more? (What about the map given by $(1\; 3)$? What about the identity map? Importantly, automorphisms form a group; what group is it?) If you apply the permutation $f = (2\;5)$, the edge between $1$ and $2$ will turn into an edge appearing between $f(1) = 1$ and $f(2) = 5$, which you don't want, so this doesn't give you an automorphism.

Answer 2

Observe that the three automorphisms $a=(1,4)(2,5)(3,6), b=(1,3), c=(4,6)$ generate the full automorphism group $Aut(H)$, and that there are thus 8 automorphisms. In other words, every automorphism can be obtained by effecting a combination of these three. More specifically, to effect an automorphism, we can choose whether or not to flip about the vertical line in the middle, and there are 2 ways to make that decision. Thereafter, we choose whether or not to flip the first leg (1,3), and there are 2 ways to decide this, and similarly 2 ways for the right leg. Any permutation of the vertex set which is an automorphism of this graph can be effected by a sequence of these three decisions. Thus there are exactly 8 automorphisms. Thus $G:=Aut(H) \le S_6$ has order 8.

To prove there are exactly 8 automorphisms and no others (and more generally, to find the number of elements in a group), we can use the orbit-stabilizer lemma. Given a permutation group $G \le Sym(X)$, to find $|G|$, pick any $x \in X$, and the lemma states that the number of elements in $|G|$ is equal to the size of the orbit of $x$ under the action of $G$ times the size of the stabilizer of $x$ in $G$, i.e. $|G|=|x^G|~|G_x|$. In our case, let $x$ be the vertex 2. Then $x$ can be mapped by an automorphism either to itself or to 5, hence the orbit of $x$ under the action of all automorphisms of $H$ is exactly $x^G=\{2,5\}$. The stabilizer $G_x$ is the set of automorphisms of $H$ that fix the vertex $x$. If an automorphism fixes 2, it must fix 5. It can swap 1 and 3 (or fix them pointwise), and it can swap 4 and 6 (or fix them pointwise). The number of elements in $G_x$ is thus $2 \times 2=4$. Thus, $|G|=2 \times 4=8$. Alternatively, you can take $x$ to be the vertex 1, say. In this case $|G_x|=2, |x^G|=4$, whence $|G|=8$. In other words, if we know $|x^G|$ and $|G_x|$ for some $x \in X$, then we can use that information to find $|G|$.

In addition to the number of automorphisms, we are often interested in exactly which group $G$ is. Since $ab \ne ba$, $G$ is nonabelian. It can be shown (by group theory) that there are exactly two nonisomorphic groups of order 8 that are not abelian, namely the dihedral group $D_8$ of symmetries of a square, and the quaternion group. Since the number of elements of order 2 in the quaternion group is only 1, whereas our $G$ has at least two elements of order 2 (namely, the elements $a,b$), it follows that $G$ cannot be the quaternion group and hence $G \cong D_8$.