Suppose I have a connected graph $G$ that is vertex-transitive. Fix a vertex $v$ in $G$ and let $h$ be an automorphism of graph $G$. If $v$ is adjacent with $h(v)$ and $G$ is symmetric, I need to show that $h$ and the stabilizer of $v$ generate $Aut(G)$.

This problem is from Algebraic Graph Theory by Norman Biggs.

I'm having a brain dead. Attempted to show it directly with connectivity but failed. Used the symmetric property but couldn't cover all cases.

Any help is appreciated. Thanks.


Let $A = {\rm Aut}(G)$, let $A_v$ be the stabilizer of $v$ in $A$, and let $B = \langle A_v, h \rangle$. We have to show that $A=B$. Since $A_v \le B$, it is sufficient to prove that $B$ acts transitively on vertices. In other words, we have to show that all vertices lie in the orbit $v^B$ of $v$ under $B$.

Let $N(v)$ be the set of vertices adjacent to $v$. Then, since $G$ is symmetric, $G_v$ acts transitively on $N(v)$. Since $h(v) \in N(v)$, we have $N(v) \subseteq v^B$.

Now, since $G$ is connected, for any vertex $w$, there is a sequence $v_0=v,v_i,\ldots,v_n=w$ of vertices in which $v_i,v_{i+1}$ are adjacent for all $i$. We show by induction on $n$ that $w \in v^B$. This is clear for $n=0$ and we proved it for $n=1$ in the previous paragraph. By induction we may assume that $v_{n-1} \in v^B$. So there exists $g \in A$ with $v^g=v_{n-1}$. Then $A_{v_{n-1}} = gA_vg^{-1} \le B$.

Now, since $v$ and $h(v)$ are adjacent in $G$, so are $g(v)=v_{n-1}$ and $gh(v)$. Then, since $G$ is symmetric, there exists $f \in A_{v_{n-1}} \le B$ with $fgh(v) = v_n$, so $w = v_n \in v^B$, which completes the induction.

| cite | improve this answer | |
  • $\begingroup$ Thank you, Sir. I understand the rest of the proof except the part that says "It is sufficient to prove B acts transitively". Why is it sufficient? $\endgroup$ – user297210 Dec 9 '15 at 10:00
  • $\begingroup$ Each stabilizer is in $B$. What about the automorphisms that fix no vertex? $\endgroup$ – user297210 Dec 9 '15 at 10:44
  • $\begingroup$ I got it. Thanks a lot.. $\endgroup$ – user297210 Dec 9 '15 at 11:10

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.