# Is there a simple graph with an odd number of automorphisms (except $1$ and $3$)?

The simple graphs upto $11$ vertices do not have $5,7,9,...$ automorphisms, in other words, the only odd numbers appearing are $1$ and $3$. Is this true for all graphs ?

Formulated as an existence-question :

• Is there an odd number $k\ge 5$ and a simple graph G with $|Aut(G)|=k$?

In particular, is there a simple graph with $5$ automorphisms ?

I found Frucht's theorem on Wikipedia.
http://en.wikipedia.org/wiki/Frucht%27s_theorem
According to this theorem, any finite group occurs as the automorphism group of a finite, undirected graph.

• The caley-graphs are mentioned in the proof-idea. Can anything be said about the smallest graph realizing a concrete group ? – Peter Oct 29 '14 at 13:26
• Wikipedia states that, starting from the caley-graph, a undirected graph can be constructed with the same automorphism-group, but the description is very abstract and no example is given. – Peter Oct 29 '14 at 13:32

An old paper of Frucht (referenced on the wikipedia page on graph automorphisms) contains the following results (Theorems 3.1 and 3.2):

If $n>2$, then there is a cubic graph $G$ on $6n$ vertices with $\text{Aut}(G)\simeq \mathbb{Z}_n$.

If $n>3$, then there is a graph $G$ on $3n$ vertices with $\text{Aut}(G)\simeq \mathbb{Z}_n$.

Note also that the proofs explicitly constructs the required graph.

• It seems to me that the constraint in the final statement here can be weakened to $n > 1$. The paper mentions that Frucht did not find an example for $n=3$ but, unless I am mistaken, imgur.com/4GmPiIu is an example. (And this construction generalizes to $n>3$, too.) – Mees de Vries Oct 29 '14 at 13:51
• Mathworld gave me the desired answer. Start with the n-cycle. Over every edge, construct a rectangular and add an edge in each of these rectangulars. I found out that the edges must be chosen in such a way that they do not share a common vertex. The resulting graph has Z(n) as automorphism group and therefore order n. What remains is to find the smallest CUBIC graph with a given order, which exists due to an extension to Frucht's theorem. – Peter Oct 30 '14 at 14:45
• The constructed graph due to mathworld need not be the smallest one. – Peter Oct 30 '14 at 14:47