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?



Reconstructing a graph given access to its 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.


