We present two new approaches to constructing graph sparsifiers - weighted
subgraphs for which every cut has the same value as the original graph, up to a
factor of $(1 \pm \epsilon)$. The first approach independently samples each
edge $uv$ with probability inversely proportional to the edge-connectivity
between $u$ and $v$. The fact that this approach produces a sparsifier resolves
an open question of Bencz\'ur and Karger. Concurrent work of Hariharan and
Panigrahi (2010) also resolves this question. The second approach samples
uniformly random spanning trees.