Frucht's theorem (original) (raw)

From Wikipedia, the free encyclopedia

The Frucht graph, a 3-regular graph whose automorphism group realizes the trivial group.

Frucht's theorem is a result in algebraic graph theory, conjectured by Dénes Kőnig in 1936[1] and proved by Robert Frucht in 1939.[2] 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.[3]

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 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.[4]

Special families of graphs

[edit]

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[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. Gert Sabidussi 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 {\displaystyle k\geq 3} {\displaystyle k\geq 3} for regular graphs and k ≥ 2 {\displaystyle k\geq 2} {\displaystyle k\geq 2} for _k_-chromatic graphs).[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.[3] It is possible to realize every finite group as the group of symmetries of a strongly regular graph.[7] 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.[8]

However, some important classes of graphs are incapable of realizing all groups as their symmetries. Camille Jordan characterized the symmetry groups of trees as being the smallest set of finite groups containing the trivial group and closed under direct products with each other and wreath products with symmetric groups;[9] in particular, the cyclic group of order three is not the symmetry group of a tree. Planar graphs are also not capable of realizing all groups as their symmetries; for instance, the only finite simple groups that are symmetries of planar graphs are the cyclic groups and the alternating group A 5 {\displaystyle A_{5}} {\displaystyle A_{5}}.[10] More generally, every minor-closed graph family is incapable of representing all finite groups by the symmetries of its graphs.[11] László Babai conjectures, more strongly, that each minor-closed family can represent only finitely many non-cyclic finite simple groups.[12]

Infinite graphs and groups

[edit]

Izbicki extended these results in 1959 and showed that there were uncountably many infinite graphs realizing any finite symmetry group.[13] Finally, Johannes de Groot and Sabidussi in 1959/1960 independently proved that any group (dropping the assumption that the group be finite, but with the assumption of axiom of choice) could be realized as the group of symmetries of an infinite graph.[14][15]

  1. ^ Kőnig (1936)
  2. ^ Frucht (1939)
  3. ^ a b Babai (1995), discussion following Theorem 4.1.
  4. ^ Babai (1995), Section 4.3.
  5. ^ Frucht (1949)
  6. ^ Sabidussi (1957)
  7. ^ Babai (1995), Theorem 4.3.
  8. ^ Albertson, Michael O.; Collins, Karen L. (1996), "Symmetry breaking in graphs", Electronic Journal of Combinatorics, 3 (1): R18, MR 1394549.
  9. ^ Babai (1995), Proposition 1.15. Babai dates Jordan's result to 1869, but includes only an 1895 paper of Jordan in his bibliography.
  10. ^ Babai (1995), discussion following Theorem 1.17.
  11. ^ Babai (1995), Theorem 4.5.
  12. ^ Babai (1995), discussion following Theorem 4.5.
  13. ^ Izbicki (1959)
  14. ^ de Groot (1959)
  15. ^ Sabidussi (1960)