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.
$\endgroup$ 25 Answers
$\begingroup$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.
$\endgroup$ 6 $\begingroup$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.
$\endgroup$ 3 $\begingroup$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.
$\endgroup$ 3 $\begingroup$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
$\endgroup$ $\begingroup$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()
