I have seen this question asked at least once before, but not with any real answers.


I was reading about the various reconstruction conjectures and equivalents, and I saw that the reconstruction conjecture, which uses a multi-set, has a set counterpart, the set reconstruction conjecture.


My question is: Does the edge reconstruction conjecture have a similar statement that involves the set and not the multi-set? Perhaps the minimum of four edges still applies? I've been curious about this for some time now and can't seem to reach a decisive conclusion.


Any help is appreciated!



Edge Reconstruction Conjecture
The edge-reconstruction conjecture does have an analogous statement to the set version of the reconstruction conjecture. As far as I am aware there is no graphs that are edge-reconstructible but not "set edge-reconstructible". Therefore the corresponding conjecture would (probably) state that every graph with at least four edges is set edge-reconstructible.


A few things relating to this problem have been done. First a theorem by Manvel:


**Theorem:** (in [1, Theorem 9])
*The degree sequence of a graph is a set edge-reconstructible property.*


Interestingly, Manvel also states that Hemminger's proof (1969) that edge-reconstruction is a special case of vertex-reconstruction extends to the case where we consider sets instead of multisets. However, there seems to be no set analogue of Greenwell's theorem that states that any vertex-reconstructible graph without isolated vertices also is edge-reconstructible.


**Theorem:** (in [2])
*A graph with at least four edges is set edge-reconstructible if the set of edge-deleted subgraphs has size at most two.*


[1] B. Manvel, "On reconstructing graphs from their sets of subgraphs", J. Comb. Theory B 21(2), (1976), 156-165.


[2] L.D. Andersen, S. Ding, P.B. Vestergaard, "On the set edge-reconstruction conjecture", JCMCC - Journal of Combinatorial Mathematics and Combinatorial Computing 20 (1996), 3-9.


