Set of fruit

The theorem of Frucht (after Roberto Frucht ) is a theorem from the mathematical branch of graph theory . It says that apart from isomorphism, every group appears as an automorphism group of a graph .

A smallest asymmetrical graph

An automorphism of an undirected graph , where is the set of nodes and the set of edges, is a bijective mapping with the property that two nodes are connected by an edge if and only if and are connected by an edge. The set of all automorphisms of is obviously a group and is called the automorphism group of . ${\displaystyle G=(V,E)}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle \varphi :V\rightarrow V}$ ${\displaystyle v_{1},v_{2}\in V}$ ${\displaystyle \varphi (v_{1})}$ ${\displaystyle \varphi (v_{2})}$ ${\displaystyle \mathrm {Aut} (G)}$ ${\displaystyle G}$ ${\displaystyle G}$

For an edgeless graph or for a complete graph is obviously equal to the symmetric group of of . For all other graphs is a proper subgroup of . In the extreme case , such graphs are called asymmetric . The smallest number of nodes in an asymmetric graph is 6. ${\displaystyle G=(V,\emptyset )}$ ${\displaystyle \mathrm {Aut} (G)}$ ${\displaystyle \mathrm {Sym} (V)}$ ${\displaystyle V}$ ${\displaystyle \mathrm {Aut} (G)}$ ${\displaystyle \mathrm {Sym} (V)}$ ${\displaystyle \mathrm {Sym} (V)=\{\mathrm {id} _{V}\}}$

Since, according to Cayley's theorem, every group is isomorphic to a subgroup of a symmetric group, the question arises whether every group appears as an automorphism group of a graph. This question is answered in the affirmative by the phrase of Frucht:

• Theorem of Frucht : For every group there is a graph whose automorphism group is isomorphic to this group.

This theorem was formulated and proven for finite groups by Roberto Frucht in 1938. The case of infinite groups has been independently proved by J. de Groot (1959) and G. Sabidussi (1960).

literature

• J. de Groot: Groups represented by homeomorphism groups , Mathematische Annalen (1959), Volume 138, pages 80-102
• R. Frucht: Production of graphs with a given abstract group , Compositio Mathematica (1938), Volume 6, pages 239-250
• G. Sabidussi: Graphs with given infinite group monthly books for mathematics (1960), volume 64, pages 64-67
• K. Wagner: Theory of Graphs , Bibliographisches Institut AG, Mannheim (1970), ISBN 3-411-00248-4