Give an example of a $G$ graph with a non-trivial group of automorphisms

642 Views Asked by At

Give an example of a $G$ graph with a non-trivial group of automorphisms and such that after removing any edge from $G$ we get a graph with a trivial group of automorphisms.

Simplified variant: Give an example of a G graph with a non-trivial group of automorphisms and such that after removing a certain edge from G we get a graph with a trivial group of automorphisms.

I tried to do simplified variant:

This one has identity and for example, symmetry about the dashed line::
List item
After removing a certain edge, we get a graph similar to this:
List item

However I don't know whether this is correct and how to make the more difficult option.

Can you help me?

1

There are 1 best solutions below

0
On

Lemma. There is a connected graph $H$, with trivial automorphism group, in which each vertex has degree at least $3$.

Proof. Draw a graph of order $6$, with degree sequence $3,3,2,2,1,1$, which has a trivial automorphism group. Add an isolated vertex and you have a graph of order $7$, with degree sequence $3,3,2,2,1,1,0$, which has a trivial automorphism group. Its complement is a connected graph with trivial automorphism group and degree sequence $6,5,5,4,4,3,3$.

Trivially, an empty graph (no edges) will have the property that removing any edge leaves a graph with trivial automorphism group; presumably that's not what is wanted.

Theorem. There is a nonempty graph $G$ with nontrivial automorphism group such that, for each edge $e\in E(G)$, the graph $G-e$ has trivial automorphism group.

Proof. Let $H$ be a connected graph with trivial automorphism group in which each vertex has degree at least $3$. Let $H'$ be an isomorphic copy of $H$, disjoint from $H$. Let $V(H)=\{v_1,\dots,v_n\}$ and $V(H')=\{v_1',\dots,v_n'\}$, where the vertices are labeled so that the map $v_i\mapsto v_i'$ is the isomorphism from $H$ to $H'$. Let $G$ be the graph obtained from $H\cup H'$ by adding vertices $w_1,\dots,w_n'$ and edges $w_iv_i$ and $w_iv_i'$. The graph $G$ has a nontrivial automorphism which swaps $H$ with $H'$, but for any $e\in E(G)$, the graph $G-e$ has no nontrivial automorphism.

Note that, in the graph $G$, each vertex in the set $W=\{w_1,\dots,w_n\}$ has degree $2$, while all other vertices have degree at least $4$. Hence, in the graph $G-e$, each vertex in $W$ has degree at most $2$, while all other vertices have degree at least $3$. It follows that an automorphism of $G-e$ must fix the set $W$. This is the first step in showing that $G-e$ has no nontrivial automorphism. Assuming (without loss of generality) that the missing edge $e$ was incident to no vertex in $H$, the next step would be to show that the set $V(H)$ is fixed by any automorphism of $G-e$, then that $V(H)$ is pointwise fixed, then that $W$ is pointwise fixed, and finally that $V(H')$ is pointwise fixed.