# Edge-deleted subgraphs and edge transitivity

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?

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.

• Without yet reading over your argument carefully: if the answer is "it is not necessarily true that $G$ is edge-transitive", then you should be able to give an example where $G$ is not edge-transitive - and such an example is a proof by itself, without considering any other cases. May 30, 2019 at 22:04
• @MishaLavrov I couldnt think of one so I just showed all possible cases May 30, 2019 at 22:09
• Now that you've updated the answer, why is the conclusion still "it is not necessarily true that $G$ is edge-transitive"? May 31, 2019 at 23:17

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$$?

• i still dont get how your argument shows that case 2 and case 3 dont exist May 31, 2019 at 21:20
• also for the bipartite case your last thing is not correct. If $\Delta = \delta+1$ you have that $G - \{e\}$ has exactly one vertex with $\delta-1$, and several vertices with $\delta$ and $\delta+1$, therefore if any subgraphs of the type are ismorphic we have that the $\delta-1$ vertice maps to the other $\delta-1$ vertice, with no assumption that the other end of $e$ is going to map to the corresponding end of the other $e$ May 31, 2019 at 21:27
• also thanks for your graph theory posts you've helped me alot in teaching myself graph theory May 31, 2019 at 21:29
• (1) We've shown that any graph of this type is either regular or bipartite. Your cases 2 and 3 describe graphs that are neither regular nor bipartite - so there are no such graphs. May 31, 2019 at 22:02
• (2) For the last thing: you are right that in the $\Delta = \delta+1$ case, there is no assumption that the other end of $e_1$ maps to the other end of $e_2$. This is why this case needs to be considered separately. But this still needs to be (and can be) shown to conclude that $G$ is edge-transitive. May 31, 2019 at 22:03