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]
Graph sizeedit
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 graphsedit
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 for regular graphs and 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.[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 groupsedit
Izbicki extended these results in 1959 and showed that there were uncountably manyinfinite 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]
frucht, theorem, theorem, algebraic, graph, theory, conjectured, dénes, kőnig, 1936, proved, robert, frucht, 1939, states, that, every, finite, group, group, symmetries, finite, undirected, graph, more, strongly, finite, group, there, exist, infinitely, many, . Frucht s theorem is a theorem in algebraic graph theory conjectured by Denes Konig 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 Frucht graph a 3 regular graph whose automorphism group realizes the trivial group Contents 1 Proof idea 2 Graph size 3 Special families of graphs 4 Infinite graphs and groups 5 References 5 1 SourcesProof idea editThe 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 Graph size editWith 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 editThere 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 nbsp for regular graphs and k 2 displaystyle k geq 2 nbsp 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 A5 displaystyle A 5 nbsp 10 More generally every minor closed graph family is incapable of representing all finite groups by the symmetries of its graphs 11 Laszlo Babai conjectures more strongly that each minor closed family can represent only finitely many non cyclic finite simple groups 12 Infinite graphs and groups editIzbicki 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 References edit Konig 1936 Frucht 1939 a b Babai 1995 discussion following Theorem 4 1 Babai 1995 Section 4 3 Frucht 1949 Sabidussi 1957 Babai 1995 Theorem 4 3 Albertson Michael O Collins Karen L 1996 Symmetry breaking in graphs Electronic Journal of Combinatorics 3 1 R18 MR 1394549 Babai 1995 Proposition 1 15 Babai dates Jordan s result to 1869 but includes only an 1895 paper of Jordan in his bibliography Babai 1995 discussion following Theorem 1 17 Babai 1995 Theorem 4 5 Babai 1995 discussion following Theorem 4 5 Izbicki 1959 de Groot 1959 Sabidussi 1960 Sources edit Babai Laszlo 1995 Automorphism groups isomorphism reconstruction PDF in Graham Ronald L Grotschel Martin Lovasz Laszlo eds Handbook of Combinatorics vol II North Holland pp 1447 1540 de Groot Johannes 1959 Groups represented by homeomorphism groups Mathematische Annalen 138 80 102 doi 10 1007 BF01369667 hdl 10338 dmlcz 101909 ISSN 0025 5831 MR 0119193 Frucht Robert 1939 Herstellung von Graphen mit vorgegebener abstrakter Gruppe Compositio Mathematica in German 6 239 250 ISSN 0010 437X Zbl 0020 07804 Frucht Robert 1949 Graphs of degree three with a given abstract group Canadian Journal of Mathematics 1 4 365 378 doi 10 4153 CJM 1949 033 6 ISSN 0008 414X MR 0032987 Izbicki Herbert 1959 Unendliche Graphen endlichen Grades mit vorgegebenen Eigenschaften Monatshefte fur Mathematik 63 3 298 301 doi 10 1007 BF01295203 MR 0105372 Konig Denes 1936 Theorie der endlichen und unendlichen Graphen Leipzig Akademische Verlagsgesellschaft p 5 As cited by Babai 1995 Sabidussi Gert 1957 Graphs with given group and given graph theoretical properties Canadian Journal of Mathematics 9 515 525 doi 10 4153 cjm 1957 060 7 ISSN 0008 414X MR 0094810 Sabidussi Gert 1960 Graphs with given infinite group Monatshefte fur Mathematik 64 64 67 doi 10 1007 BF01319053 MR 0115935 Retrieved from https en wikipedia org w index php title Frucht 27s theorem amp oldid 1186040293, wikipedia, wiki, book, books, library,
