Asymmetric graphs with asymmetric edge-deleted subgraphs

Question

When I say graph, I mean undirected, irreflexive graphs without multiple-edges (sometimes called a simple graph).

Call a graph $G$ “asymmetric” if the only automorphism of $G$ is the identity map. For example, the cyclic graph on $n \geq 3$ vertices is not symmetric, while the graph with one vertex and no edges is asymmetric.

Given a graph $G$, an “edge-deleted subgraph” of $G$ is a subgraph of $G$ formed by deleting exactly one edge from $G$. For example, every edge-deleted subgraph of the cyclic graph on $n \geq 3$ edges is the path graph with $n-1$ edges connecting $n$ vertices.

I am interested in the class of finite graphs $\mathcal{C}$ with the following properties. $G \in \mathcal{C}$ if and only if:

1. $G$ is asymmetric
2. If $H$ is an edge-deleted subgraph of $G$, then $H$ is asymmetric

The following two propositions are clear to me.

Proposition 1: If $G$ and $G’$ are in $\mathcal{C}$, their coproduct $G \coprod G’ \in \mathcal{C}$

Proposition 2: Let $n,i,j,k \in \mathbb{N}$ be distinct natural numbers with $n,i,j,k \geq 3$. Take the cyclic graphs on $n,i,j,k$ vertices, and join the $i,j,k$-cycles to the $n$-cycle on distinct edges. The resulting graph is in $\mathcal{C}$. An example with $(n,i,j,k) = (5,3,4,6)$ is drawn below.

The first proposition gives us a way to generate a new graph in $\mathcal{C}$ from any two graphs in $\mathcal{C}$, and the second proposition gives us an infinite family of graphs in $\mathcal{C}$.

Can anyone come up with any other interesting classes of graphs in $\mathcal{C}$? Is a complete characterization known?

Answer 1

Almost all sufficiently large graphs are in class $\mathcal C$, in the following sense: if you take $n$ vertices and choose at random between all $2^{\binom n2}$ graphs with those $n$ vertices, the probability that you'll get a graph in $\mathcal C$ tends to $1$ as $n \to \infty$.

In a 1963 paper, Erdős and Rényi proved the following, stronger statement:

Theorem 2. Let us choose at random a graph $\Gamma$ having $n$ given vertices so that all possible $2^{\binom n2}$ graphs should have the same probability to be chosen. Let $\varepsilon>0$ be arbitrary. Let $\mathbf P_n(\varepsilon)$ denote the probability that by changing not more than $\frac{n(1-\varepsilon)}{2}$ edges of $\Gamma$ it can be transformed into a symmetric graph. Then we have $$\lim_{n\to \infty}\mathbf P_n(\varepsilon) = 0.$$

Here, by a symmetric graph, Erdős and Rényi mean a graph with a nontrivial automorphism; by changing edges, they mean adding or deleting them, in any combination. This means that almost all sufficiently large graphs are not just in class $\mathcal C$: they are asymmetric, and all subgraphs with one edge deleted are asymmetric, and all subgraphs with two edges deleted are asymmetric, and all subgraphs with one edge added are asymmetric, and so on up to the limit of $\frac{n(1-\varepsilon)}{2}$.

Erdős and Rényi also prove that changing $\lfloor \frac{n-1}{2}\rfloor$ edges is always sufficient to make a symmetric graph, and so the statement of the theorem above is as strong as it could possibly be. (Intuitively, we can create an automorphism that swaps two vertices $v,w$ and leaves the rest fixed by changing only edges incident to $v$ and $w$, and by choosing $v$ and $w$ carefully, we can make sure it's enough to only change $\lfloor \frac{n-1}{2}\rfloor$ of their edges.)

---

On the other hand, neither of the propositions in the question are precisely true without being more careful:

• In proposition 1, the coproduct (or disjoint union) of two graphs in $\mathcal C$ will not be in $\mathcal C$ if the two graphs are isomorphic - or even if just a connected component of one graph is isomorphic to a connected component of the other graph. Aside from this qualification, the proposition should hold.
• In proposition 2, suppose we delete the edge that the $k$-cycle shares with the $n$-cycle. Then we have an $i$-cycle and a $j$-cycle attached to an $(n+k-2)$-cycle. If it so happens that the $i$-cycle and $j$-cycle are attached at opposite edges of the $(n-k-2)$-cycle (with $\frac{n+k}{2}-2$ edges in between them on either side), then there is now a nontrivial automorphism. This (and the related problems where we swap the roles of $i$, $j$, $k$) can be avoided by taking care where we join the $i$-, $j$-, and $k$-cycle to the $n$-cycle.