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:

  1. Each automorphism of $\hat{G_0}$ induces a unique automorphism of $G$.

  2. 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.).

  • 2
    $\begingroup$ Each automorphism of $\widehat{G}_0$ restricts to a permutation of the vertices of $G$, and I strongly suspect that if you examine the proofs of (1) and (2), you’ll find that they actually show that the two automorphism groups are identical when viewed simply as groups of permutations of the vertices of $G$. $\endgroup$ – Brian M. Scott Mar 15 '13 at 13:54
  • $\begingroup$ Well it sounds like (1) and (2) come from a bijective mapping. Have you tried verifying that the homomorphic property applies for this mapping? It sounds like if $\alpha$ and $\beta$ are automorphisms of $G$ induced by automorphisms $\hat{\alpha}$ and $\hat{\beta}$ of $\hat{G_0}$ then $\alpha\beta$ is probably induced by $\hat{\alpha}\hat{\beta}$. $\endgroup$ – Alexander Gruber Mar 15 '13 at 21:18
  • $\begingroup$ @BrianM.Scott : Don't you mean every automorphism of $G$ restricts to an automorphism of $\hat{G_0}$ as $\hat{G_0}$ has fewer vertices then $G$? And in the book there is no proof of (1); it only says "Clearly (1) is true". $\endgroup$ – Shahab Mar 16 '13 at 1:15
  • $\begingroup$ @BrianM.Scott: Please see the update above. $\endgroup$ – Shahab Mar 16 '13 at 2:49

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.