Let $G$ be a simple graph. Let $E^-(G)$ denote the set of (isomorphism classes) of subgraphs of $G$ that can be obtained by deleting a single edge of $G$. Similarly, let $E^+(G)$ be the set of (isomorphism classes) of simple graphs that can be obtained by adding a single edge to $G$. Is $G$ uniquely determined by $E^-(G)$ and $E^+(G)$? Thank you in advance!
Are there any other examples besides the two graphs on 4 vertices?
Let $V=\{a,b,c,d\}$, $E_1=\{(a,b),(a,c),(a,d)\}$, $E_2=\{a,b),(a,c),(b,c)\}$, $G_1=(V,E_1)$, and $G_2=(V,E_2)$. Then $E^-(G_1)=E^-(G_2)$ and $E^+(G_1)=E^+(G_2)$ although $G_1$ and $G_2$ are not isomorphic.
Except for finitely many cases, $G$ can be reconstructed from the largest of $E^-(G)$ and $E^+(G)$. Note that you have the edge-decks of both $G$ and its complement.
Lovász proved that $G$ is edge-reconstructible if it has more edges than its complement. That covers all cases except when $G$ has exactly $n(n-1)/4$ edges.
Müller proved that graphs with more than $n(\log_2(n)-1)$ edges are edge-reconstructible. That finishes it for all $n\ge 12$. The cases $n=10,11$ don't happen, as $n(n-1)/4$ is not an integer. So you are left with $n\le 9$ which has been done exhaustively by computer.
