# How many automorphisms does the following (labelled) graph have:

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?

-

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\}$.

-

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?

-
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