Frucht's theorem
Encyclopedia
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.
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 a number of vertices equal to the order of the group.
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
. showed that any group can be realized as the symmetry groups of countably many distinct k-regular graph
s, 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 also possible to realize every finite group as the group of symmetries of a strongly regular graph
.
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 closed under direct product
s with each other and wreath product
s with symmetric group
s; in particular, the cyclic group
of order three is not the symmetry group of a tree. Planar graph
s 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 group
s and the alternating group A5. More generally, every minor-closed graph family
is incapable of representing all finite groups by the symmetries of its graphs. László Babai
conjectures, more strongly, that each minor-closed family can represent only finitely many non-cyclic finite simple groups.
Theorem
In mathematics, a theorem is a statement that has been proven on the basis of previously established statements, such as other theorems, and previously accepted statements, such as axioms...
in algebraic graph theory
Algebraic graph theory
Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs. This is in contrast to geometric, combinatoric, or algorithmic approaches...
conjectured by Dénes Kőnig
Dénes König
Dénes Kőnig was a Jewish Hungarian mathematician who worked in and wrote the first textbook on the field of graph theory....
in 1936 and proved by Robert Frucht
Robert Frucht
Robert Wertheimer Frucht was a German-Chilean mathematician; his research specialty was graph theory and the symmetries of graphs....
in 1939. It states that every finite group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
is the group of symmetries
Graph automorphism
In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity....
of a finite undirected graph. More strongly, for any finite group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
G there exist infinitely many non-isomorphic
Graph isomorphism
In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f \colon V \to V \,\!such that any two vertices u and v of G are adjacent in G if and only if ƒ and ƒ are adjacent in H...
simple connected graphs such that the automorphism group
Graph automorphism
In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity....
of each of them is isomorphic to G.
Proof idea
The main idea of the proof is to observe that the Cayley graphCayley graph
In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem and uses a specified, usually finite, set of generators for the group...
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.
Graph size
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 graphVertex-transitive graph
In the mathematical field of graph theory, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphismf:V \rightarrow V\ such thatf = v_2.\...
, with a number of vertices equal to the order of the group.
Special families of graphs
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. proved that in fact countably many 3-regular graphsCubic graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....
with the desired property exist; for instance, the Frucht graph
Frucht graph
In the mathematical field of graph theory, the Frucht graph is a 3-regular graph with 12 vertices, 18 edges, and no nontrivial symmetries. It was first described by Robert Frucht in 1939....
, a 3-regular graph with 12 vertices and 18 edges, has no nontrivial symmetries, providing a realization of this type for the trivial group
Trivial group
In mathematics, a trivial group is a group consisting of a single element. All such groups are isomorphic so one often speaks of the trivial group. The single element of the trivial group is the identity element so it usually denoted as such, 0, 1 or e depending on the context...
. showed that any group can be realized as the symmetry groups of countably many distinct k-regular graph
Regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
s, k-vertex-connected graphs
K-vertex-connected graph
In graph theory, a graph G with vertex set V is said to be k-vertex-connected if the graph remains connected when you delete fewer than k vertices from the graph...
, or k-chromatic graphs
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
, 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
Birkhoff's representation theorem
In mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any finite distributive lattice can be represented as finite sets, in such a way that the lattice operations correspond to unions and intersections of sets...
to a finite distributive lattice
Distributive lattice
In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection...
, 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
Median graph
In mathematics, and more specifically graph theory, a median graph is an undirected graph in which any three vertices a, b, and c have a unique median: a vertex m that belongs to shortest paths between any two of a, b, and c.The concept of median graphs has long been studied, for instance by or ...
. It is also possible to realize every finite group as the group of symmetries of a strongly regular graph
Strongly regular graph
In graph theory, a discipline within mathematics, a strongly regular graph is defined as follows. Let G = be a regular graph with v vertices and degree k...
.
However, some important classes of graphs are incapable of realizing all groups as their symmetries. Camille Jordan
Camille Jordan
Marie Ennemond Camille Jordan was a French mathematician, known both for his foundational work in group theory and for his influential Cours d'analyse. He was born in Lyon and educated at the École polytechnique...
characterized the symmetry groups of trees
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
as being the smallest set of finite groups closed under direct product
Direct product of groups
In the mathematical field of group theory, the direct product is an operation that takes two groups and and constructs a new group, usually denoted...
s with each other and wreath product
Wreath product
In mathematics, the wreath product of group theory is a specialized product of two groups, based on a semidirect product. Wreath products are an important tool in the classification of permutation groups and also provide a way of constructing interesting examples of groups.Given two groups A and H...
s with symmetric group
Symmetric group
In mathematics, the symmetric group Sn on a finite set of n symbols is the group whose elements are all the permutations of the n symbols, and whose group operation is the composition of such permutations, which are treated as bijective functions from the set of symbols to itself...
s; in particular, the cyclic group
Cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...
of order three is not the symmetry group of a tree. Planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
s 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 group
Cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...
s and the alternating group A5. More generally, every minor-closed graph family
Robertson–Seymour theorem
In graph theory, the Robertson–Seymour theorem states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering...
is incapable of representing all finite groups by the symmetries of its graphs. László Babai
László Babai
László Babai is a Hungarian professor of mathematics and computer science at the University of Chicago. His research focuses on computational complexity theory, algorithms, combinatorics, and finite groups, with an emphasis on the interactions between these fields...
conjectures, more strongly, that each minor-closed family can represent only finitely many non-cyclic finite simple groups.