# Reconstructing a graph given access to its cut function

Given an unweighted graph $G = (V, E)$, let the cut function on this graph be defined to be: $C:2^V \rightarrow \mathbb{Z}$ such that: $$C(S) = |\{(u,v) \in E : u \in S \wedge v \not\in S\}|$$ Suppose you have the ability to query $C$, but otherwise have no knowledge of the edge set $E$. Is it possible to reconstruct $G$ by making only polynomial (in $|V|$) many queries to the cut function?

-

## 1 Answer

Asking individual vertices, you figure out the valence of each vertex with $n$ questions. Asking for pairs of vertices, you can then decide if each pair has an edge between them or not: they have an edge if and only if the "degree" on the pair is two less than the sum of the "degrees". Thus you can reconstruct the graph with $n+\binom{n}{2}$ questions.

-
Of course, in the answer $n$ is the number of vertices of the graph. –  M P Aug 24 '10 at 18:24
Thanks -- of course you are correct! I have obviously oversimplified the question I am interested in. I will revise to make the question less trivial –  Aaron Aug 24 '10 at 18:26
Actually, perhaps I will just create a new question, and accept your answer -- you did answer the question I asked, after all. –  Aaron Aug 24 '10 at 18:28