1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ What did you try? Where did you get stuck? Is there something that prevents you from solving this on your own? Why do you think the answer $6 (n-2)!$? Have you tried calculating the answer for small values of $n$, say $n=1,2,3,4,5$? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Jan 25 '18 at 18:49
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Jan 25 '18 at 18:49
  • $\begingroup$ I have written some part of my work, hope this helps. Thanks. $\endgroup$ – mori Jan 26 '18 at 10:03
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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