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.
Edit: 16 vertices is indeed the smallest possible size for such a graph (see the proof below).
Here's an example of a graph with 16 vertices whose automorphism group is $Q_8$. As we will show, the automorphisms of the graph preserve the colors and arrows:
The symmetry of this graph is similar to the symmetry of the Cayley graph of $Q_8$ shown in the question above. Here's an argument that it's possible to recover the colors and arrows from the structure of the graph itself:
Cyan vertices have degree 7, while yellow vertices have degree 5.
Black edges connect pairs of yellow vertices.
Green edges connect vertices of different colors and do not share triangles with black edges.
Purple edges connect cyan vertices and are involved in triangles with green edges.
Red edges connect vertices of different colors and are involved in triangles with green and purple edges.
Blue edges connect vertices of different colors and are neither red nor green.
Cyan edges connect cyan vertices and are not purple.
Each black edge is involved in exactly one black-red-blue triangle, and the arrow points from the vertex opposite the red edge to the vertex opposite the blue edge.
Using the colors and arrows, it's easy to prove that any automorphism of this graph that fixes a vertex must fix all 16 vertices, so there are at most eight automorphisms. It's easy to check that there are in fact eight automorphisms, which form a copy of $Q_8$.
Incidentally, Babai constructs a 16-vertex graph for $Q_8$ in his paper "On the minimum order of graphs with given group" with 52 edges. The graph above is a slight improvement on this, having the same number of vertices but only 48 edges. Though 16 is the minimum possible number of vertices, it would be interesting to know whether there's a 16-vertex graph with fewer than 48 edges that has symmetry group $Q_8$.
Edit: 16 vertices is indeed the minimum possible. Indeed, any graph whose automorphism group is $Q_8$ must have at least two orbits of size $8$.
To see this, observe first that any faithful action of $Q_8$ on a graph must have at least one orbit of size $8$, since otherwise the action factors through $Q/\{\pm 1\}$.
Now, suppose we have a faithful action of $Q_8$ on a graph $G$, and suppose that $G$ has just one orbit of size $8$. Let $v$ be a vertex in this orbit. I claim that switching $v$ with $-1v$ is an automorphism of $G$. This automorphism is not in $Q_8$, since the action of $Q_8$ on the orbit of size $8$ is the left regular action, so it follows that the automorphism group of $G$ is larger than $Q_8$.
To prove that switching $v$ and $-1v$ is an automorphism of $G$, observe that:
If $w$ is any vertex not in the orbit of size $8$, then the stabilizer of $w$ is a proper subgroup of $Q_8$, so $-1w = w$. Thus, there is an edge from $v$ to $w$ if and only if there is an edge from $-1v$ to $w$.
If there is an edge from $v$ to $iv$, then its image under $i$ is an edge from $iv$ to $-1v$. Thus $v$ is connected by an edge to $iv$ if and only if $-1v$ is connected by an edge to $iv$. The same holds for $-iv$, $\pm j v$, and $\pm k v$.
This proves the claim, and therefore 16 is the smallest possible size.
Best Answer
Let $I$ be the identity isomorphism, and let $M$ be the mirroring isomorphism. We want to determine whether there exist any other isomorphisms.
In order to do this, let's imagine that there exists an isomorphism that I'll denote $F_1$ which is unequal to either $I$ or $M$. Let's see what we can learn about $F_1$; maybe we will be able to prove a contradiction, or maybe we will be able to find a construction of $F_1$.
An isomorphism must respect the valences of vertices. There are exactly two vertices of valence $2$, namely vertex 5 and vertex 6, and therefore $F_1$ either fixes 5 and 6, or $F_1$ interchanges them. Define a new automorphism $F_2$:
Either way, we have produced an isomorphism $F_2$ that fixes $5$ and $6$.
Furthermore, $F_2$ is different from $I$ (because in Case 1, if $F_2=I$ then $M_1 F_1 = I$ and so $F_1 = M_1^{-1}=M_1$; or if $F_1=F_2=I$; and in either case we get a contradiction).
Next, I look in the graph for all paths between $5$ and $6$. There is just one path of length $3$, namely 5---8---7---6. An isomorphism must take paths to paths and must respect lengths of paths. Therefore $F_2$ take this path to itself and it also fixes the endpoints, and it follows that $F_2$ fixes $7$ and $8$.
Since $F_2$ fixes $5$ it must either fix both $2$ and $8$ or interchange them, but we've just shown it fixes $8$ so it also fixes $2$. By a similar argument $F_2$ fixes $4$.
I think you should probably be able to continue from here, showing that $F_2$ fixes $1$ and $9$ and $10$, and therefore $F_2 = I$. This is a contradiction, and therefore $F_1$ did not exist.