Give a connected graph whose automorphism group has size 3

1.4k Views Asked by At

Find a connected graph whose automorphism group has size 3.

Note: I know such graph must be non-simple.

1

There are 1 best solutions below

4
On BEST ANSWER

Every group is isomorphic to the automorphism group of a simple graph (see Frucht's Theorem), including the cyclic group of order $3$.

To construct a simple graph $G$ whose automorphism group has size $3$, take $K_3$ and, for each edge, replace it by a copy of a graph $G$ with no non-trivial automorphisms ($F$ say, which could be the Frucht graph). [This operation needs to be performed in the same way for each edge.]

Any automorphism of $G$ must map a copy of $F$ to another copy of $F$, which, since $F$ has no non-trivial automorphisms, can be achieved in precisely $3$ ways. (Any other automorphisms would give rise to a non-trivial automorphism of $F$.)

Here's a drawing:

A simple graph with automorphism group of size 3

(thanks to Mathematica)