TOPICS
Search

Frucht's Theorem


Frucht's theorem states that every finite group is the automorphism group of a finite undirected graph. This was conjectured by König (1936) and proved by Frucht (1939). In fact, the stronger statement may be made that for any finite group, there exist infinitely many non-isomorphic simple connected graphs whose automorphism groups are isomorphic to the original graph.


See also

Automorphism Group, Finite Group, Frucht Graph, Graph Automorphism

Explore with Wolfram|Alpha

References

Frucht, R. "Herstellung von Graphen mit vorgegebener abstrakter Gruppe." Compos. Math. 6, 239-250, 1939.König, D. Theorie der endlichen und unendlichen Graphen. New York: Chelsea, 1950.

Cite this as:

Weisstein, Eric W. "Frucht's Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/FruchtsTheorem.html

Subject classifications