Graph representation using edge sets
I think you can build $G$ in iterations: 


$M$ contains all $(v, \{e\})$ where $v \in \Gamma(v_0)$ ($\Gamma$ being neighborhood); so you can identify all edges to nodes that are distance 1 from $v_0$, as well as the nodes themselves; you can also identify the edges between nodes in $\Gamma(v_0)$ by looking for pairs $(v, \{e_1, e_2\})$, where $v \in \Gamma(v_0)$ and $e_1$ is an edge between $v_0$ and some $u \in \Gamma(v_0)$.
then, iteratively, you can identify all edges and nodes in the subgraph of $G$ induced on the vertices which are distance at most $i$ to $v_0$ (call it $G_{i}$), using $G_{i-1}$. The idea is the same as above: you look for pairs $(v, S)$, where all but one edges in $S$ are in $G_{i-1}$; this gives $V(G_i \setminus G_{i-1})$. Then you can identify edges between vertices $u, v \in V(G_i \setminus G_{i-1})$ by looking for pairs $(v, S)$, where $S = S&#39; \cup \{e_1\} \cup \{e_2\}$, such that $S&#39; \subseteq E(G_{i-1})$, and $e_1$ has one point in $G_{i-1}$ and the other point is $u$; $e_2$ is the edge $(u, v)$.


Are you aware of the reconstruction and edge reconstruction conjectures? They have the same spirit as your probelm and, as far as I know, are open. Check out this beautiful half page proof by Lovasz that the edge reconstruction conjecture is true for any graph that has more edges than its compliment.