# Graph recovery from pairwise-common neighborhoods

Define the common neighborhood of two vertices $$u$$ and $$v$$ of a simple undirected graph as the set $$N(u,v)=N(u)\cap N(v)$$. For a simple bipartite graph $$G=(U,V,E)$$, define the pairwise-common neighborhoods set as $$\{N(u_1,u_2):u_1\not=u_2\in U∧N(u_1,u_2)≠∅\}$$.

1. Is it possible to recover a bipartite $$G$$ if given only its pairwise-common neighborhoods set? Assume $$G$$ connected and degree greater or equal than 2 for all vertices.
2. Is there an efficient algorithm that constructs some bipartite graph with a given pairwise-common neighborhoods set, or halts if one does not exist?
• – smapers Mar 25 at 17:25
• As stated (with the set given as input, without multiplicities), the answer to question 1 is no. Given just the pairwise-common neighborhood set, without multiplicities, you can't distinguish the complete bipartite graphs $K_{n, 2}$ from $K_{n', 2}$ for any integers $n, n'\ge 2$. – Neal Young Mar 31 at 15:37