I am trying to understand the proof of Frucht's theorem which is:
Every finite group is isomorphic to the automorphism group of some
simple graph.
The proof (which I am reading from this book) begins as follows: Let $\Gamma=\{g_1,\cdots, g_n\}$ be a group. Consider a directed graph $\hat{G_0}$ with $V(\hat{G_0})=\Gamma$ and a directed edge between $g_i$ and $g_j$ colored $k$ where $g_ig_j^{-1}=g_k$.
Next it goes on to show that $Aut(\hat{G_0})\approx\Gamma$.
Next, a graph $G$ is constructed: Whenever $g_i$ has a directed edge leading into $g_j$ of color $k$, then that edge is replaced by a (non-directed) path of length $k+2$. In this $k+2$-path there are paths of length $1$ attached to each inner point except for the inner point next to $g_j$ where we attach a path of length $2$.
Then the following is established:
-
Each automorphism of $\hat{G_0}$ induces a unique automorphism of $G$.
-
If $\alpha$ is an automorphism of $G$, then $\alpha$ is induced by some automorphism of $\hat{G_0}$.
This finishes the proof.
What I don't understand is as the last two points presumably only establish that $Aut(\hat{G_0})$ and $Aut(G)$ have the same cardinality. It doesn't establish that they are isomorphic as groups which is essential for the final conclusion that $Aut(G)\approx \Gamma$.
Update: There is no proof of (1) provided in the book. Instead it just says that the proof is clear! I assume what is meant is this: For any automorphism $f$ of $\hat{G_0}$, we construct an automorphism of $G$ by first permuting $V(G_0)$ as per $f$, then rearranging the paths appropriately (the path joining $g_i$ and $g_j$ is send to the path joining $f(g_i)$ and $f(g_j)$. The structure of the paths is such that there is no permutation possible within a particular path.).
Best Answer
Claim 1 is indeed quite clear as the permutation $f$ of the vertices of $\hat G_0$ induces the corresponding permutation of the "special" vertices of $G$ and if a directed edge $ab$ of colour $k$ is mapped to a directed edge $f(a)f(b)$ (also of colour $k$) then the induced automorphism of $G$ maps the inbetween vertices of the corresponding $k+2$ path from $a$ to $b$ to the corresponding vertices of the $k+2$ path from $f(a)$ to $f(b)$, and accordingly for the attached length 1 paths.
Claim 2 is based on the observation that $\hat G_0$ can be reconstructed from $G$: Vertices of degree $1$ are clearly from the attachments to the vertices of the paths used as replacements for coloured edges, vertices of degree $2$ signify the beginning of such paths and so we recognize which vertices correspond to original vertices of $\hat G_0$ (namely those with degree $\ge3$ having no leaf as neighbour) and between which such vertces there is an edge of ehich colour in which direction. Especially, an automorphism of $G$ permutes the set of vertices with degree $\ge3$ having no leaf as neighbour, i.e. permutes the vertices of $\hat G_0$ and the automorphism must also map paths to paths of the same length and with "begin" marker at the same end, i.e. we get a matching map for the edges of $\hat G_0$.
This means that $\operatorname{Aut}(G)$ can be viewed as a group of permutations of $\Gamma$ ("the group $\operatorname{Aut}(G)$ acts faithfully on the set $\Gamma$") and per the construction this action is the same as that of $\operatorname{Aut}(\hat G_0)$, hence $\operatorname{Aut}(G)\cong \operatorname{Aut}(\hat G_0)\cong \Gamma$.
I remember giving an explicit construction of a graph here, but that was for the case of a directed acyclic graph. You can try to produce an alternate proof of Frucht's theorem from that as well - again by replacing a directed edge with a replacement graph having trivial automorphism group, for example a length $4$ path with one end "marked" with a degree $1$ vertex as in your source.