Number of automorphisms of graphs of bounded valences Given a finite graph G of valence 3. Is there a (good) upper bound (maybe a constant depending on the number of edges) on the number of automorphisms of G?
I try to find on google if someone did it before, but I cannot find anything.
 A: I would guess the worst case is n/4 copies of $K_4$. Here you get $(n/4)!24^{n/4}$ automorphisms.
A: If disconnected cubic graphs are allowed, then probably user36212's answer is best possible for $n$ a multiple of 4. Is there a simple proof?
If only connected cubic graphs are considered, Opstall and Verliche found the best possible bound. It is somewhat messy so I won't state it here.
Here on mathoverflow I asked the same question for 3-connected cubic graphs. It remains unsolved.
A: Assuming that you are working with a 3-regular graph $G$, here is an elementary upper bound for the number of automorphisms $f:G\rightarrow G$. Denote the number of vertices of $G$ by $n$. Starting from a vertex $v$, there are at most $n$ choices for $f(v)$. The three vertices connected to $v$ should be mapped to the tree vertices connected to $f(v)$ which is possible in $3!$ ways. Next, pick one of the $n-4$ vertices left, say $w$. There are at most $n-4$ choices for $f(w)$ and $3!$ ways to determine the image under $f$ of vertices connected to $w$. Proceeding like this, we obtain the upper bound 
$6^{\lceil\frac{n}{4}\rceil}\prod_{0\leq4i<n}(n-4i)$ for $\big|{\rm{Aut}}(G)\big|$.   
