0
$\begingroup$

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?

2 Answers 2

4

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

2

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?

  • 0
    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 are2012-11-07