Edge-deleted subgraphs and edge transitivity

Question

The question I am working on is:

Let $G$ be a graph all of whose edge-deleted subgraphs are isomorphic. Is $G$ necessarily edge-transitive?

My answer is as follows:

Let $\mathfrak{F}$ be the family of all edge-deleted subgraphs of $G$, and define $F_{e} = G/e$; suppose $G$ has a single component. Let $d = (d_{1},\ldots,d_{n})$ be the degree sequence of $G$. Suppose that any $F_{e},F_{e'} \in \mathfrak{F}$ are isomorphic. When we remove an edge we subtract $1$ from two elements of $d$; suppose $\psi_{G}(e) = e(v_{i},v_{j})$ and $\psi_{G}(e') = e(v_{i},v_{k})$, then for their degree sequences to be equivalent we require that $d(v_{j}) = d(v_{k})$, and thus all neighbors of $v_{i}$ must have the same degree. If $d(v_{i}) = d(v_{j})$ then our graph is $\Delta$-regular, and if not then we can bipartition $G$ to $G[X_{\delta},X_{\Delta}]$ s.t. all vertices in the same partition have the same degree (there can be at most two partitions).

$\textbf{Case 1}$: $G$ is $\Delta$-regular. If $G$ is $\Delta$-regular then the isomorphism between $F_{e}$ and $F_{e'}$ must induces an automorphism s.t. $e$ is mapped to $e'$, because their ends are the only vertices that have degree $\Delta-1$.

$\textbf{Case 2}$: $G[X_{\delta},X_{\Delta}]$ is bipartite; let $e,e' \in E(G)$ have $\psi_{G}(e) = e(u,v)$ and $\psi_{G}(e') = e(u',v')$ with $d(u)=d(u') = \Delta$ and $d(v)=d(v') = \delta$. If $\Delta > \delta+1$, for $F_{e},F_{e'} \in \mathfrak{F}$ we have that the isomorphism between $F_{e}$ and $F_{e'}$ must induce an automorphism that maps $e$ to $e'$ because their ends are the only ones that have degrees $\delta-1$ and $\Delta-1$. If $\Delta = \delta+1$ then $v$ maps to $v'$ because they are the only vertices with degree $\delta-1$, and $u$ maps to $u'$ because they are in the same partition - otherwise $u$ would be mapped to some $w \in V(X_{\delta})$, which cant be true for $\Delta > 2$; this would imply the existence of an edge between elements of $X_{\delta}$. Thus $G$ is edge-transitive for $\Delta > 2$.

Thus it is not necessarily true that $G$ is edge-transitive. If $G$ has multiple components then the same logic applies to each component; we only get edge-transitivity if $G$ is $\Delta$-regular, if $G$ can be partitioned into a $\Delta$-regular subgraph ($\Delta > 1$) with additional isolated vertices, or if $G[X_{\delta},X_{\Delta}]$ as a whole is bipartite (with $\Delta > 2$) s.t. all vertices in the same partition have the same degree allowing a possible third partition with isolated vertices.

Does this logic make sense?

EDIT : A user below pointed out a flaw in my old logic, but this result covers all cases.

Answer 1

There is a flaw in your logic.

We are considering all graphs $G$ such that all their edge-deleted subgraphs are isomorphic. You say: "if $G$ is $\Delta-\delta+1$-partite with $\Delta-\delta+1>2$, then it is not edge-transitive". But are there really graphs, all of whose edge-deleted subgraphs are isomorphic, that are $\Delta-\delta+1$-partite with $\Delta-\delta+1>2$?

If there are no such graphs, then it is still possible that all graphs whose edge-deleted subgraphs are isomorphic are edge-transitive.

---

In fact, there are no graphs as above. Let $G$ be a graph such that all of $G$'s edge-deleted subgraphs are isomorphic. We may assume that $G$ has no isolated vertices, because they don't change the problem at all. Let $\Delta$ be the maximum degree of $G$, and let $\delta$ be its minimum degree.

Let $e$ be an edge of $G$. The number of vertices of degree $\Delta$ in $G-e$ is $0$, $1$, or $2$ less than the number of vertices of degree $\Delta$ in $G$, depending on whether edge $e$ was incident to $0$, $1$, or $2$ such vertices. If all edge-deleted subgraphs are isomorphic, then all their degree sequences are the same, so every edge is incident to the same number of maximum-degree vertices.

Similarly, the number of vertices of degree $\delta-1$ in $G-e$ is $0$, $1$, or $2$, depending on whether edge $e$ was incident to $0$, $1$, or $2$ vertices of degree $\delta$. Therefore every edge is incident to the same number of minimum-degree vertices.

There are two possibilities:

1. $G$ is $\Delta$-regular, and so every edge is incident to $2$ vertices of degree $\Delta$. (Corresponding to your Case 1.)
2. $G$ is bipartite, with bipartition $(X,Y)$, such that every vertex in $X$ has degree $\Delta$ and every vertex in $Y$ has degree $\delta \ne \Delta$. (Corresponding to your Case 4.)

In particular, your Case 2 and Case 3 cannot occur. So it's not valid to say "$G$ is not necessarily edge-transitive because it's not edge-transitive in cases 2 and 3" because cases 2 and 3 are impossible.

You have already shown that in the regular case, $G$ must be edge-transitive, by looking at degree sequences.

You have also mostly analyzed the bipartite case, but you need to be a bit more careful: if $\Delta=\delta+1$, then an edge-deleted subgraph $G-e$ has a vertex of degree $\delta-1$, some vertices of degree $\delta$, and some vertices of degree $\delta+1$. One former endpoint of $e$ is the vertex of degree $\delta-1$, but the other endpoint can't be located by looking at vertex degrees alone.

Can you find another distinguishing feature of the other former endpoint of $e$, so that you can show that in any isomorphism between $G - e_1$ and $G - e_2$ (where $e_1, e_2$ are two edges) the endpoints of $e_1$ are mapped to the endpoints of $e_2$?