Satz von Frucht

Der Satz von Frucht (nach Roberto Frucht) ist ein Satz aus dem mathematischen Teilgebiet der Graphentheorie. Er besagt, dass bis auf Isomorphie jede Gruppe als Automorphismengruppe eines Graphen auftritt.

Datei:Kleinster asymmetrischer Graph.svg

Ein kleinster asymmetrischer Graph

Ein Automorphismus eines ungerichteten Graphen $G=(V,E)$, wobei $V$ die Knotenmenge und $E$ die Kantenmenge ist, ist eine bijektive Abbildung $\varphi :V\rightarrow V$ mit der Eigenschaft, dass zwei Knoten $v_{1},v_{2}\in V$ genau dann durch eine Kante verbunden sind, wenn $\varphi (v_{1})$ und $\varphi (v_{2})$ durch eine Kante verbunden sind. Die Menge $\mathrm {Aut} (G)$ aller Automorphismen von $G$ ist offenbar eine Gruppe und heißt die Automorphismengruppe von $G$.

Für einen kantenlosen Graphen $G=(V,\emptyset )$ oder für einen vollständigen Graphen ist $\mathrm {Aut} (G)$ offenbar gleich der symmetrischen Gruppe von $\mathrm {Sym} (V)$ von $V$. Für alle anderen Graphen ist $\mathrm {Aut} (G)$ eine echte Untergruppe von $\mathrm {Sym} (V)$. Im Extremfall ist $\mathrm {Sym} (V)=\{\mathrm {id} _{V}\}$, solche Graphen nennt man asymmetrisch. Die kleinste Knotenzahl eines asymmetrischen Graphen ist 6.

Da nach dem Satz von Cayley jede Gruppe isomorph zu einer Untergruppe einer symmetrischen Gruppe ist, stellt sich die Frage, ob jede Gruppe als Automorphismengruppe eines Graphen auftritt. Diese Frage wird durch den Satz von Frucht positiv beantwortet:

• Satz von Frucht: Zu jeder Gruppe gibt es einen Graphen, dessen Automorphismengruppe isomorph zu dieser Gruppe ist.

Dieser Satz wurde 1938 von Roberto Frucht für endliche Gruppen formuliert und bewiesen. Der Fall unendlicher Gruppen wurde unabhängig voneinander von J. de Groot (1959) und G. Sabidussi (1960) bewiesen.

Literatur

• J. de Groot: Groups represented by homeomorphism groups, Mathematische Annalen (1959), Band 138, Seiten 80–102
• R. Frucht: Herstellung von Graphen mit vorgegebener abstrakter Gruppe, Compositio Mathematica (1938), Band 6, Seiten 239–250
• G. Sabidussi: Graphs with given infinite group Monatshefte für Mathematik (1960), Band 64, Seiten 64–67
• K. Wagner: Graphentheorie, Bibliographisches Institut AG, Mannheim (1970), ISBN 3-411-00248-4