If all the edge-deleted subgraphs of a finite graph are isomorphic then the graph is edge-transitive. <a href="http://www.newcastle.edu.au/school-old/math-physical-science/our_staff/downloads/macdougall_jim_onereductions.pdf">Here</a> is a possible reference, though you might want to look at <a href="http://staff.um.edu.mt/jlau/research/SURV_ARS.ps">this</a> 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 finite graphs and small $k$, having $k$ edge orbits is the same as having $k$ isomorphism classes of edge deleted subgraphs, as is proved <a href="http://www.springerlink.com/content/h321401n5046718w/">here</a>.