Frucht's theorem

More strongly, for any finite group G there exist infinitely many non-isomorphic simple connected graphs such that the automorphism group of each of them is isomorphic to G. The main idea of the proof is to observe that the Cayley graph of G, with the addition of colors and orientations on its edges to distinguish the generators of G from each other, has the desired automorphism group.

With a larger set of exceptions, most finite groups can be represented as the symmetries of a vertex-transitive graph, with a number of vertices equal to the order of the group.

Frucht[5] proved that in fact countably many 3-regular graphs with the desired property exist; for instance, the Frucht graph, a 3-regular graph with 12 vertices and 18 edges, has no nontrivial symmetries, providing a realization of this type for the trivial group.

[6] From the facts that every graph can be reconstructed from the containment partial order of its edges and vertices, that every finite partial order is equivalent by Birkhoff's representation theorem to a finite distributive lattice, it follows that every finite group can be realized as the symmetries of a distributive lattice, and of the graph of the lattice, a median graph.

[8] However, some important classes of graphs are incapable of realizing all groups as their symmetries.

[12] Izbicki extended these results in 1959 and showed that there were uncountably many infinite graphs realizing any finite symmetry group.