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?
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.

$\begingroup$ Of course, in the answer $n$ is the number of vertices of the graph. $\endgroup$– M PAug 24 '10 at 18:24

$\begingroup$ 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 $\endgroup$– AaronAug 24 '10 at 18:26

3$\begingroup$ Actually, perhaps I will just create a new question, and accept your answer  you did answer the question I asked, after all. $\endgroup$– AaronAug 24 '10 at 18:28