Ungerichteter Graph/Automorphismengruppe/3 Knoten/Aufgabe/Kommentar

Zunächst sollte man beachten, dass die Automorphismengruppen zweier isomorpher Graphen isomorph sind (Aufgabe). Es reicht also aus, die Automorphismengruppe eines Graphen in jeder „Isomorphieklasse“ (im Sinne von Aufgabe) zu bestimmen.

Es gibt 4 Isomorphieklassen von Graphen mit 3 Knotenpunkten, die der Anzahl der Kanten entsprechen: 0, 1, 2 und 3. Offensichtlich ist ein Graph mit 0 oder 3 Kanten homogen und seine Automorphismengruppe ist die Permutationsgruppe ${}S_{3}$. Sei nun ${}G=(V,E)$ ein Graph mit einer Kante. Wir können annehmen, dass ${}V=\{1,2,3\}$ und ${}E=\{1,2\}$. Dann muss der Punkt ${}\{3\}$ durch jeden Automorphismus von ${}G$ auf sich selbst abgebildet werden (wieso?), während die Punkte ${}\{1\}$ und ${}\{2\}$ austauschbar sind. Somit ist die Automorphismengruppe von ${}G$ die Permutationsgruppe ${}S_{2}$. Der Fall, dass ${}G$ zwei Kanten hat, kann ähnlich behandelt werden.

Die obigen Berechnungen von Automorphismengruppen veranschaulichen eine allgemeinere Tatsache: jeder Graph und sein komplementärer Graph besitzen isomorphe Automorphismengruppen (siehe

Aufgabe.) Diese Tatsache ist nützlich, wenn man die Automorphismengruppen sämtlicher Graphen mit ${}n$ Knotenpunkten bestimmen will: man muss nur jene Graphen mit höchstens ${}{\frac {1}{2}}{\binom {n}{2}}$ Kanten betrachten.

Zur kommentierten Aufgabe