  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,\tilde{w})$ with at most $\lceil d(n-1)
\rceil$ edges such that for every $x \in \mathbb{R}^{V}$, \[ x^{T}L_{G}x \leq
x^{T}L_{H}x \leq (\frac{d+1+2\sqrt{d}}{d+1-2\sqrt{d}})\cdot x^{T}L_{G}x \]
where $L_{G}$ and $L_{H}$ are the Laplacian matrices of $G$ and $H$,
respectively. Thus, $H$ approximates $G$ spectrally at least as well as a
Ramanujan expander with $dn/2$ edges approximates the complete graph. We give
an elementary deterministic polynomial time algorithm for constructing $H$.
