Skip to main content
2 of 3
added 38 characters in body
Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402

If all the edge-deleted subgraphs of a graph are isomorphic then the graph is edge-transitive. Here is a possible reference, though you might want to look at this survey on pseudosimilarity. (Pseudosimilar edges give isomorphic subgraphs after being deleted but are not part of the same orbit under the automorphism group of the graph). For small $k$, having $k$ edge orbits is the same as having $k$ isomorphism classes of edge deleted subgraphs, as is proved here.

Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402