## CSDM - Twice-Ramanujan Sparsifiers

We prove that every graph has a spectral sparsifier with a number of edges linear in its

number of vertices. As linear-sized spectral sparsifiers of complete graphs are expanders, our

sparsifiers of arbitrary graphs can be viewed as generalizations of expander graphs.

In particular, we prove that for every d > 1 and every undirected, weighted graph G =

(V,E,w) on n vertices, there exists a weighted graph H = (V, F, ~w) with at most dn edges

such that for every x ∈ ℜ^{V} ,