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

Recall that a graph $G$ is arc transitive if the natural action of $\mathrm{Aut}(G)$ on $A(G) = \{ (u,v) | \{u,v\} \in E(G)\}$ is transitive.

In other words, given $(u,v),(u'.v') \in A(G)$ one finds a $g \in \mathrm{Aut}(G)$ such that $g (u,v) := (g(u),g(v)) = (u',v').$

Our lecturer said it is not completely straightforward to show that $K_n$ is an arc transitive graph. As far as I can see since $\mathrm{Aut}(K_n) = S_n$ one can always find a suitable permutation that maps a pair of vertices into another pair of vertices thus showing that $K_n$ is indeed arc transitive.

Am I missing something? I recall the lecturer talked about considering some cases (i.e if the arcs are not disjoint) but I don't see how this could create any real obstacle in finding the suitable permutation.

Am I missing something crucial here?

share|cite|improve this question
It might help if you told us what $K_n$ is. Is it the complete graph on $n$ vertices? If so, the problem amounts to showing that $S_n$ acts 2-transitively, which I would agree is not very taxing (assuming $n \ge 2$). – Derek Holt Oct 27 '12 at 13:03
up vote 0 down vote accepted

$S_n$ acting transitively on $K_n$ only gives you that for each two vertices $v,v'\in V(K_n)$, there is a $\sigma\in S_n$ so that $v\sigma=v'$. You want to show that for any four vertices $v,w,v',w'\in V(K_n)$ (with $v,w$ distinct, as well as $v',w'$), you can find a $\sigma$ so that $v\sigma = v'$ and $w \sigma = w'$. This means $S_n$ has to be $2$-transitive, which is stronger than just transitive. For example, $D_n$ is transitive but not $2$-transitive for any $n> 3$, which is easy to see visually by its action on the $n$-cycle.

share|cite|improve this answer

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.