Graph/Kantengraph/Automorphismengruppe/Aufgabe/Lösung

1. Wir definieren

   $\operatorname {Aut} \,G\longrightarrow \operatorname {Aut} \,K,\,f\longmapsto \Psi (f):={\left(\{u,v\}\mapsto \{f(u),f(v)\}\right)}.$

   Einem Automorphismus ${}f$ des Graphen wird also die Abbildung auf der Kantenmenge zugeordet, die eine Kante auf die Bildkante (!) unter ${}f$ abbildet. Die Gesamtabbildung ist wegen

   ${}{\begin{aligned}(\Psi (f\circ g))(\{u,v\})&=\{(f\circ g)(u),(f\circ g)(v)\}\\&=\{f(g(u)),f(g(v))\}\\&=(\Psi (f))(\{g(u),g(v)\})\\&=(\Psi (f))((\Psi (g))(\{u,v\}))\\&=(\Psi (f)\circ \Psi (g))(\{u,v\})\end{aligned}}$

   ein Homomorphismus in das Monoid der Abbildungen auf der Kantenmenge. Wegen

   ${}\Psi (f)\circ \Psi (f^{-1})=\Psi (f\circ f^{-1}))=\operatorname {Id} _{K}\,$

   gehört das Bild von ${}\Psi$ zur Permutationsgruppe der Kantenmenge. Es ist noch zu zeigen, dass ${}\Psi (f)$ ein Automorphismus des Kantengraphen ist. Es sei also ${}f$ ein Graphautomorphismus und seien ${}e,e'\in K$ Kanten, die im Kantengraph adjazent sind. Das bedeutet, dass sie im Graphen ${}G$ koinzident sind und daher ist ${}e=\{u,v\}$ und ${}e'=\{u,w\}$. Dann sind auch ${}\Psi (f)(e)=\{f(u),f(v)\}$ und ${}\Psi (f)(e')=\{f(u),f(w)\}$ koinzident und somit adjazent im Kantengraphen.

2. Wir betrachten den linearen Graphen mit zwei Punkten. Seine Automorphismengruppe ist neben der Identität durch die Vertauschung der beiden Punkte gegeben. Der Kantengraph ist einpunktig und hat triviale Automorphismengruppe.

3. 

   

   
   

   Es sei ${}G$ der vollständige Graph zu vier Punkten mit dem zugehörigen Kantengraphen (siehe Skizzen). Wir betrachten den Automorphismus des Kantengraphen, der ${}b$ und ${}d$ vertauscht und ${}a,c,e,f$ auf sich selbst abbildet. Da sowohl ${}b$ als auch ${}d$ im Kantengraphen mit ${}a,c,e,f$ verbunden sind, liegt ein Automorphismus vor. Wir behaupten, dass man diesen nicht durch einen Graphautomorphismus von ${}G$ realisieren kann. Es sei ${}h$ ein solcher Homomorphismus. Da die Kanten ${}a$ und ${}e$ auf sich selbst abgebildet werden, muss ${}1$ auf sich abgebildet werden. Deshalb müssen auch ${}2$ und ${}3$ auf sich selbst abgebildet werden und ${}h$ muss die Identität sein. Dann ist aber auch ${}\Psi (h)$ die Identität.

Zur gelösten Aufgabe