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

An automorphism of a graph $G$ is an isomorphism between $G$ and $G$ itself. How many automorphisms does the following (labelled) graph have:

$K_n − e$, i.e. the graph obtained from a complete graph with n vertices by deleting exactly one edge?

share|cite|improve this question

HINT: Let $u$ and $v$ be the vertices of the deleted edge. The vertices of the graph come in only two flavors: $u$ and $v$, and all the rest. Thus, If $f:V\to V$ is your isomorphism, the only restriction on $f$ is that it be a flavor-preserving bijection: $f[\{u,v\}]=\{u,v\}$.

share|cite|improve this answer

Say your graph $K_n - e$ is called $H$. The automorphisms of $H$ are the same as the automorphisms of the complement of $H$. But the complement of $H$ has only one edge, so perhaps it is not too hard to figure out what its automorphisms look like?

share|cite|improve this answer
sorry do you mean that the complement of $H$ has only one edge? – user46220 Nov 6 '12 at 23:51
Yes; sorry for the error. – MJD Nov 6 '12 at 23:52
I can imagine what the picture would look like, we have the complete graph minus 1 edge, but then can you give me an example of an isomorphism because I think there is only one iso. for one edge on two vertices? – user46220 Nov 6 '12 at 23:54
Do you know how many automorphisms $K_5$ has? – MJD Nov 6 '12 at 23:56
so it's a bijection on the vertices that preserves the edges, so if edge A connects u,v then: f(u), f(v) will have to be connected,but a complete graph has all vertcies connected. So would I be right in saying that any bijection will be an automorphism, so I just need to know how many bijections there are – user46220 Nov 7 '12 at 0:08

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.