# Estimating graphs using random cuts

How easy is it to estimate a graph by observing only a few random cuts? Is there prior work related to this? I did google but could not find anything concrete.

Any help would be appreciated. Thanks.

• What does "estimate a graph" mean? Estimate the number of vertices/edges in a graph? – Huck Bennett Apr 27 '12 at 7:55
• @HuckBennett By estimation, i mean recovering the graph with their edge weights. – Vedarun May 8 '12 at 5:04

Its not clear what you want to estimate, or what you mean by looking at a random cut. But it is hard to learn much about a graph by just observing the size of a random cut. This is because a random cut will always cut $m/2$ edges in expectation (where $m$ is the number of edges in the graph), independent of the structure of the graph. Of course, the entire graph can be thought of as a vector of length ${n \choose 2}$, so if you get to observe the -exact- size of that many random cuts, because they are likely to be linearly independent, you can reconstruct the graph. There's nothing special about cuts here: you're just observing the exact value of the dotproduct of $d$ linearly independent vectors with an unknown vector of length $d$, and this system of linear equations will have an exact solution.