How to prove a graph asymmetric?

Solution 1:

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.

Solution 2:

Start with the idea to make a highly symmetric cubic graph that has one vertex $v$, that is so special that it necessarily must be a fixed point of any automorphism, then make minor changes that do not affect the exceptional position of $v$ but that break all symmetries.

For a concrete case I started with the special property: $v$ is the center of the graph: it is the unique vertex realizing the radius of the graph. Now draw the following graph: $v$ is in the center, its neighbours are $0,1,2$, labeled counterclockwise. Now grow 2 more 'generations': draw two neighbours of $0$, further outwards, label them $00$ and $01$ counterclockwise, ditto for $1$ and $2$, and for the third generation draw two neighbours of $00$, further outwards, label them $000$ and $001$ and ditto for the 5 other second generation vertices. Now you have drawn a nice symmetric tree where each internal node has degree 3. Finally connect the leaves counterclockwise: $000$ with $001$, $001$ with $010$ etc. We now have a highly symmetric cubic graph with 22 vertices $(1+3+6+12)$.

$v$ has a distance of at most $3$ to any other vertex and it is easy to see that it is the only vertex with this property. Now the only thing left to do is make minor modifications in the three "branches" (offspring of 0, offspring of 1 and offspring of 2) that satisfy 4 conditions

• Cubicity is preserved
• The special position of $v$ is preserved
• The branches get different modifications
• All symmetry is gone

The second condition guarantees that $v$ will still be a fixed point for any automorphism. The third condition guarantees that $0$, $1$ and $2$ will also be fixed points (well, not entirely, but already the second try was succesful). The fourth condition is to fulfill the requirement for this question. Note however that it is now relatively easy to check since we have a 'fixed base'.

Because we only grew three generations the modifications in the branches can be minor, in this case we just remove two nonadjacent edges $pq$ and $rs$ and replace them with $pr$ and $qs$ as follows:

• In the 0-branch we remove an outer edge and a third generation edge: we remove $\{000,001\}$ and $\{01,010\}$ and replace them with $\{01,001\}$ and $\{000,010\}$.
• In the 1-branch we change nothing at all.
• In the 2-branch we remove two outer edges that connect vertices with the same parent: we remove $\{200,201\}$ and $\{210,211\}$ and replace them by $\{200,210\}$ and $\{201,211\}$.

Note that the branches still have internal symmetries, but since they are also tied to each other all global symmetries are eliminated.

Also note that after the modification in the 0-branch $v$ is no longer the unique center, but it is still special enough: $v$ still has 20 vertices at distance at most 2, all other vertices have less than 16 vertices at distance at most 2.

I used nauty for an independent verification that the final graph indeed is asymmetric. Here is the sample dreadnaut session that shows that there are indeed no automorphisms.

> n=22 g
 0 : 1 2 3 ;
 1 : 4 5 ;
 2 : 7 15 ;
 3 : 8 9 ;
 4 : 10 11 ;
 5 : 11 13 ;
 6 : 14 15 16 ;
 7 : 16 17 ;
 8 : 18 19 ;
 9 : 20 21 ;
10 : 12 21 ;
11 : 12 ;
12 : 13 ;
13 : 14 ;
14 : 15 ;
15 : ;
16 : 17 ;
17 : 18 ;
18 : 20 ;
19 : 20 21 ;
20 : ;
21 : .
> x
level 1:  1 cell; 22 orbits; 0 fixed; index 1/22
22 orbits; grpsize=1; 0 gens; 23 nodes (21 bad leaves); maxlev=2
cpu time = 0.00 seconds
>

Picture of the graph before manipulation

Picture of the graph after manipulation (unfortunately the tool decided to mirror the image, but I am sure your brains are able to cope with such a minor discomfort)

(Thanks to MJD for showing me how to do pictures)

Generalization to larger graphs is straightforward. I have written a computer program that generates these graphs for an arbitrary number of generations (well, until it runs out of memory, which will be quick considering the exponential growth) and then performs the same minor modifications (lifted to the 'highest' generation). The results have proven to be asymmetric by nauty. Graphs in DOT format or dreadnaut input format are available on request.

There is also a simple plausibility argument that there cannot be an automorphism. $v$ as center of the graph must be a fixed point. The unmodified branch 1 has no 4-cycles, but branch 0 has a cluster of 3 4-cycles whose distance to 0 is easily seen to be smaller than its distance to 1 or 2. Branch 2 gets 2 4-cycles and an analogous argument applies. This assures that indeed 0,1 and 2 must be fixed points as well and this will be enough to fix the rest of the graph.