Frucht's theorem

Frucht's theorem is a theorem in algebraic graph theory conjectured by Dénes Kőnig in 1936 and proved by Robert Frucht in 1939. It states that every finite group is the group of symmetries of a finite undirected graph. 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. Therefore, if each of these edges is replaced by an appropriate subgraph, such that each replacement subgraph is itself asymmetric and two replacements are isomorphic if and only if they replace edges of the same color, then the undirected graph created by performing these replacements will also have G as its symmetry group.

With three exceptions – the cyclic groups of orders 3, 4, and 5 – every group can be represented as the symmetries of a graph whose vertices have only two orbits. Therefore, the number of vertices in the graph is at most twice the order of the group. With a larger set of exceptions, most groups can be represented as the symmetries of a vertex-transitive graph, with a number of vertices equal to the order of the group.

There are stronger versions of Frucht's theorem that show that certain restricted families of graphs still contain enough graphs to realize any symmetry group. Frucht (1949) 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. Sabidussi (1957) showed that any group can be realized as the symmetry groups of countably many distinct k-regular graphs, k-vertex-connected graphs, or k-chromatic graphs, for all positive integer values k (with k ≥ 3 for regular graphs and k ≥ 2 for k-chromatic graphs). 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. It is possible to realize every finite group as the group of symmetries of a strongly regular graph. Every finite group can also be realized as the symmetries of a graph with distinguishing number two: one can (improperly) color the graph with two colors so that none of the symmetries of the graph preserve the coloring.

...
Wikipedia