Find minimal simple graph, such that its automorphism group is isomorphic to the Klein four-group

Question

Minimal meaning that $|V|+|E|$ is minimal (sum of number of vertices and edges). The graph is not necessarily connected.

How do I find this graph, and how do I prove minimality and unicity? Any ideas?

Answer 1

$V_4\cong C_2\times C_2$, so $|V|=4, |E|=1$ has the right automorphism group, and there would be very few smaller graphs to check by hand.

---

A little more dignified than exhaustive search would be something like:

The automorphism group of a graph with $n$ vertices corresponds to a subgroup of $S_n$. From Lagrange's theorem we now know that we need $n!$ to be a multiple of $4$, so we're looking for a graph with at least $4$ vertices. $4$ or $5$ isolated points won't do (the automorphism group of that is far too large), but if we add a single edge we happen to get the right group. And now it is clear that we can't get through with any smaller $|V|+|E|$.