  The Kadison-Singer Conjecture, as proved by Marcus, Spielman, and Srivastava
(MSS) [Ann. Math. 182, 327-350 (2015)], has been informally thought of as a
strengthening of Batson, Spielman, and Srivastava's theorem that every
undirected graph has a linear-sized spectral sparsifier [SICOMP 41, 1704-1721
(2012)]. We formalize this intuition by using a corollary of the MSS result to
derive the existence of spectral sparsifiers with a number of edges linear in
their number of vertices for all undirected, weighted graphs. The proof
consists of two steps. First, following a suggestion of Srivastava [Asia Pac.
Math. Newsl. 3, 15-20 (2013)], we show the result in the special case of graphs
with bounded leverage scores by repeatedly applying the MSS corollary to
partition the graph, while maintaining an appropriate bound on the leverage
scores of each subgraph. Then, we extend to the general case by constructing a
recursive algorithm that repeatedly (i) divides edges with high leverage scores
into multiple parallel edges and (ii) uses the bounded leverage score case to
sparsify the resulting graph.
