Showing that a specific regular graph has a trivial automorphism group

Question

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?

Answer 1

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.

Answer 2

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:

1. 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.
2. 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.
3. 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.

Answer 3

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.