Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider the graph $G$ in the following picture A cubic graph with a trivial automorphism It can be verified (using Sage or an equivalent program) that $G$ has a trivial automorphism.

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?

share|improve this question

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer
    
Thanks for the reply. Do you happen to see a quick argument why automorphisms preserve distances as you described? –  Jernej Nov 2 '12 at 16:12
    
Sure. First, we establish it for vertices. If $u$ and $v$ are vertices, then there is a path with length $d(u, v)$ from $u$ to $v$. Under $\varphi$ this path goes to a path of the same length that connects $\varphi(u)$ and $\varphi(v)$, therefore $d(\varphi(u), \varphi(v)) \leqslant d(u, v)$. Applying the same to $\varphi^{-1}$ we can show that $d(\varphi(u), \varphi(v)) \geqslant d(u, v)$, and we are done. –  Dan Shved Nov 2 '12 at 16:23
    
And second, once we know this for vertices, it becomes obvious that $d(\varphi(A), \varphi(B)) = d(A, B)$ for any sets of vertices $A$ and $B$. –  Dan Shved Nov 2 '12 at 16:24

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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