Showing that a specific regular graph has a trivial automorphism group Consider the graph $G$ in the following picture 
 
It can be verified (using Sage or an equivalent program) that $G$ has a trivial automorphism group.
What I am wondering is how to show this fact by a formal (by hand) proof that uses the least amount possible of case analysis. Anyone happens to see a short proof?
 A: Well, here is my attempt.
First, we observe that there are 3 triangles: $A=\{1, 5, 9\}, \,B=\{0, 8, 4\}$ and $C=\{2, 6, 11\}$. If $\varphi$ is an automorphism, then it should act as a permutation of ${A, B, C}$. Now, looking at the distances between triangles, we see that $d(A, B)=d(A, C)=1$ and $d(B, C)=2$. Therefore, $\varphi$ should send $A$ to itself.
So, $\varphi$ somehow permutes vertices $\{1, 5, 9\}$. Now we look at the distances from these vertices to the triangles $B$ and $C$. $d(1, B)=d(1,C)=2$, $d(5, B)=d(9, C)=1$ and $d(5, C)=d(9, B)=2$. From this it is clear that $\varphi(1)=1$, and $\varphi(\{5, 9\}) = \{5, 9\}$.
From the above it follows that $\varphi(7)=7$. Now, $d(7, B)=1$ and $d(7, C)=2$. Therefore, $\varphi(B)=B$ and $\varphi(C)=C$. From this we see that $\varphi(5)=5$ and $\varphi(9)=9$.
So now we know that $\varphi$ fixes vertices $1, 5, 9, 7$. From this it is already clear that $\varphi$ is the identity.
This doesn't look very short, but it doesn't involve any case analysis either.
A: The general approach is first to find specific points that must be fixed under an automorphism, then proceed inductively using the following sorts of logic:


*

*If a node is known to be fixed, and all but one of its neighbors are known to be, then we know that all neighbors must be fixed.

*If two nodes are known to be fixed, and there is only one simple path of length $k$ between those two nodes, then all the nodes on that path must be fixed.

*If two neighboring nodes are fixed, and there is only one cycle of length $k$ containing those two nodes and the edge between them, then all the nodes on that cycle must be fixed.


First part: Show specific nodes are fixed
The set of nodes not on any triangle is $\{3,7,10\}$. Any automorphism must restrict to an automorphism of the sub-graph on these three nodes. In particular, it must send $3$ to $3$, and thus $3$ must be fixed.
There is only one edge between $3$ and  a node on a triangle. Since $3$ is fixed, that edge must be fixed, and therefore it's other end must be fixed.  So $11$ must be fixed.
Second part: Induction
Since $3$ and $11$ are fixed, and there is only one cycle of length $4$ containing the edge $\{3,11\}$, then the other nodes of that cycle, $6$ and $10$, must be fixed. (Rule 3.)
Since $3$ and two neighbors $11,10$ are fixed, $7$ must be fixed (Rule 1.)
Since $6$ and $11$ are fixed, and there is only one cycle of length $3$ containing the edge between them, the third point on that cycle, $2$, must be fixed. (Rule 3.)
Since $7$ and $10$ are fixed, and there is only one path of length $3$ between them, the other points on that path, $0,4$ must be fixed. (Rule 2.)
Since $0,4$ are fixed, $8$ must be fixed. (Rule 3.)
Since $7,0,3$ are fixed, $1$ is fixed. (Rule 1.)
Since $1,8$ fixed, and there is only one path of length $2$ between them, the point in between, $5$ must be fixed. (Rule 2.)
Finally, $9$ is fixed because all the other nodes are fixed.
A: Just say something special about each vertex. Remove the vertices participating in a triangle. You are left with 7-3-10 whence 3 stays fixed. 11 is the only neighbor of 3 participating in a triangle, so 11 stays fixed. 11-10-6-3 is the unique shortest chain from 11 to 3 that is not just the edge joining them, so 10 and 6 are fixed and thereby 7 stays fixed. So now it is 3,6,7,10,11. 11-2-9-1-7 is the unique shortest chain from 11 to 7 not involving the vertices we fixed already, so 2,9, and 1 cannot move. Similarly, 10-4-0-7 is the unique shortest chain from 10 to 7 bypassing the already fixed vertices, so 0,4 stay put.
Now we have only 5 and 8 left and about 100 reasons not to be able to swap them.
Still boring, but also no casework anywhere.
