Can any graph be approximated by a sparse graph? Surprisingly, the answer is "yes", under several notions of approximation.

In 1996, Benczur and Karger proved that, for any graph on n vertices, there is an efficient algorithm to decrease its number of edges to only O(n log n / epsilon2) while preserving all cuts of the graph to within a factor 1+epsilon.

In 2008, Batson, Spielman and Srivastava strengthened this result, showing that there is an efficient algorithm to decrease its number of edges to only O( n / epsilon2 ) while preserving all cuts and all eigenvalues to within a factor 1+epsilon.

I find these results to be very interesting because (1) the statements themselves are surprising, (2) the proofs are glorious, and (3) there are numerous applications. For example, these results are now heavily used in algorithms for cut and flow problems, and they play a key role in the recent nearly-linear-time algorithms for solving symmetric, diagonally dominant linear systems.