Number of automorphism for clique of 6 vertices minus two non adjacent edges

Question

How many automorphism does a clique with 6 vertices have, when we take two edges from it (two edges that don't have the same vertex)?

I thought the answer is 6*(n-2)! Number of automorphism for a full graph Kn is n!. Clique can be seen as a full graph since all of the vertices must be connected to each other. Since we take away two edges I think it should be (n-2)!. And it has to be multiplied by 6 because there are 6 vertices all together so was still permutate them.

Is this correct? How to find this correctly? What if there are N vertices?

Answer 1

It's not hard to check that $(1\; 2)$, $(1\;3)(2\;4)$, and $(5\;6)$ are all automorphisms of the graph. Considering the degrees of vertices, this shows that the orbits of the automorphism group $G$ are $\{1,2,3,4\}$ and $\{5,6\}$. According to the orbit stabilizer theorem, $|G| = 4|G_1|$. Once again, it's not hard to check that $(3\;4)$ and $(5\;6)$ are automorphisms in $G_1$, and consider degrees and the property of being connected to $1$ shows that the orbits of $G_1$ are $\{3,4\}$ and $\{5,6\}$. It is not hard to check that all 4 permutations respecting these orbits are in $G_1$, and so $|G_1| = 4$. We conclude that $|G| = 16$.

Informally, $1$ can get mapped to any of $1,2,3,4$. Assuming that $1$ gets mapped to itself (without loss of generality), we see that $2$ has to get mapped to itself, $3$ to one of $3,4$, and $5$ to one of $5,6$. These are the only constraints, so in total there are $4\cdot 2\cdot 2 = 16$ automorphisms.

Answer 2

The automorphism group of a graph and of its complement are isomorphic. Hence, the problem is to find the automorphism group of the complement graph, which consists of $2$ disjoint edges and two isolated vertices. The two isolated vertices can be permuted among themselves (in $2$ ways). The two edges can be permuted among themselves (in $2$ ways) and the endpoints of each edge can further be permuted (in $2^2=4$ ways). Thus, the total number of automorphisms is $2 \times 2 \times 2^2 = 16$.

The structure of the automorphism group can also be obtained. The group of the two isolated vertices is $S_2$. The group of the two independent edges is the wreath product of $S_2$ with $S_2$. Hence, the automorphism group of the graph is $S_2 \times (S_2~wr~S_2)$.

More generally, it is shown in [Frucht, On the groups of repeated graphs. Bull. Amer. Math. Soc, 55 (1949), 418-420.] that if a graph $G$ consists of $k$ connected copies of some graph $H$, then the automorphism group of $G$, denoted $Aut(G)$, is the wreath product of $S_k$ with $Aut(H)$, which contains automorphisms of the individual copies as well as automorphisms that permute the copies among themselves.