How to prove a graph asymmetric? Find a 3-regular graph that is has no other automorphism other than the identity.
I searched and found that this means the graph is asymmetric and there is an example: the Frucht graph. But can someone show me how to prove this property? If you have a link please just post it here. Thanks.
 A: Draw the Frucht graph as

Let $U$ be the set of vertices that are fixed under every automorphism.
There is only one 4-cycle $(9-10-11-12)$, so any automorphism maps that to itself.
There is only one 5-cycle $(8-9-12-11-10)$ that contains the vertices in that 4-cycle.
So $8 \in U$  (since $8$ is the only member of that 5-cycle that is not in the 4-cycle).  
$7 \in  U$ (the only vertex that is a neighbour of $8$ and is not in the 4-cycle).  
$2 \in U$ (the only vertex at distance 4 from $8$).  
$3 \in U$ (the only vertex at distance 3 from $7$ and also at distance 3 from $8$).
$4 \in U$ (the only other member of a triangle containing $2$ and $3$). 
$5 \in U$ (the only vertex adjacent to $4$ and $7$).
$6 \in U$ (the only other member of a triangle containing $5$ and $7$).
... etc.
A: You are right that this problem is hard: in fact, the problem of testing whether a given graph has a trivial automorphism group belongs to the class of NP-complexity, and it is unknown whether there exists an algorithm that can check this property in polynomial time (i.e., the number of steps the algorithm takes is a polynomial function of the number of vertices of the graph).  
However, I can give you a proof that the Frucht graph has a trivial automorphism group.  This is the proof given by Frucht himself in his paper "Graphs of degree three with a given abstract group".  
First, label the vertices of the graph as shown: 

Notice that the graph is $3$-regular: every vertex has precisely three neighbours.  This allows us to define the type $(\kappa,\lambda,\mu)$ of a vertex $V$ as follows:
Write the three neighbours of $V$ as $V_1$, $V_2$ and $V_3$.  
Recall that a cycle of length $\nu$ is defined as a finite sequence of vertices $v_1,v_2,\dots,v_\nu$ such that no two $v_i$ are the same, and we have $v_i\sim v_{i+1}$ ($\sim$ means 'is connected to') for all $i=1,\dots,\nu-1$, and $v_\nu\sim v_1$; i.e., a loop of $\nu$ different vertices connected by edges.  For example, $A,B,F,E$ is a cycle of length $4$.  
We now let $\kappa$ be the smallest $\nu$ such that there exists a cycle of length $\nu$ containing the edges $VV_1$ and $VV_2$ (In general, such a cycle might not exist.  In that case, set $\kappa=\infty$.).  Similarly set $\lambda$ to be the smallest $\nu$ such that there exists a cycle of length $\nu$ containing the edges $VV_1$ and $VV_3$, and $\mu$ to be the smallest $\nu$ such that there exists a cycle of length $\nu$ containing the edges $VV_2$ and $VV_3$.  The type of $V$ is then the triple $(\kappa,\lambda,\mu)$.  Since the order in which we labelled the vertices $V_1,V_2,V_3$ is completely arbitrary, we may assume that $\kappa\leq\lambda\leq\mu$.  
Let's try and find the type of vertex $A$.  $A$ has three neighbours - $B$, $E$ and $M$.  The shortest cycle containing the edges $AB$ and $AE$ is the cycle $A,B,F,E$, which has length $4$.  The shortest cycle containing the edges $AB$ and $AM$ is $A,B,C,D,M$, which has length $5$.  The shortest cycle containing the edges $AE$ and $AM$ is $A,E,F,B,C,D,M$, which has length $7$.  Therefore, the type of $A$ is $(4,5,7)$.  
You can go through the graph computing types for the vertices.  Then you get the types as follows: 
$$\begin{array}{lCr}
A & \cdots & (4,5,7) \\
B & \cdots & (4,5,6) \\
C & \cdots & (5,5,6) \\
D & \cdots & (3,5,5) \\
E,F & \cdots & (3,4,5) \\
G,H & \cdots & (3,6,7) \\
J,K,L,M & \cdots & (3,5,6)
\end{array}$$
It is very easy to see that if $\tau$ is an automorphism of the graph, then the type of $\tau(V)$ is the type of $V$ for any vertex $V$.  It follows that if there exist $\kappa\leq\lambda\leq\mu$ such that there is exactly one vertex with type $(\kappa,\lambda,\mu)$ then that vertex is fixed by $\tau$.  Hence, any automorphism of the graph must fix the vertices $A,B,C,D$.  
Now an automorphism $\tau$ must either fix $E$ and $F$ or swap them round (since they are the only vertices of type $(3,4,5)$).  Since $A\sim E$ and $A\nsim F$, we know that $\tau(A)\sim\tau(E)$ and $\tau(A)\nsim\tau(F)$; i.e., $A\sim\tau(E)$ and $A\nsim\tau(F)$ (since $\tau$ fixes $A$).  That means that $\tau$ fixes $E$ and $F$.  
A similar argument shows that $\tau$ must fix $G$ and $H$: it must either fix them or swap them, but $G$ is connected to $E$ (which we know is fixed) and $H$ isn't, so they have to be fixed.  
Now we've fixed $A,B,C,D,E,F,G,H$, we know that $J$ is fixed (since it's the unique common neighbour of $C$ and $H$), and therefore that $K$ is fixed (since it's the unique common neighbour of $J$ and $H$), and therefore that $L$ is fixed (since it's the unique common neighbour of $K$ and $D$), and therefore that $M$ is fixed (since all the other vertices are fixed).  So $\tau$ must be the identity.  $\Box$
In general, if you want to show that a graph has no symmetries, considering the types $(\kappa, \lambda, \mu)$ of vertices (or some other invariant) is the way to go.  If you know German (which I don't), then this paper by Frucht gives some insight into how you might come up with such a graph.  
A: 
The pictures of the posts of Robert Israel and Donkey_2009 are chosen very instructive. Here a way that used the picture of Donkey_2009 to add more node to the Frucht Graph. Removing all points the lie on triangles. For the remaining points a unique isomorphism can be derived. The extension of this isomorphism to the other points is unique too. 
The picture of Robert Israel can be used too to find an extension:

Forget the green nodes and edges. For the remaining Node with black and blue nodes there exists only one isomorphism 
$\phi$ with 
$$\text{color}(\phi(\text{node}))=\text{color}(\text{node}) \tag{1}$$
Now we add the red edges (three or more, adjacent to this red dotted edge). The graph has only one isomorphism of type $(1)$. 

Now for each blue node we add the green nodes again and get an antisymmetric graph again
A: The lazy way to do the original assignment in Sage.
sage: for G in graphs.nauty_geng("12 -d3 -D3"):
         if G.automorphism_group().order() == 1:
            G.show()


