  Motivated by the problem of routing reliably and scalably in a graph, we
introduce the notion of a splicer, the union of spanning trees of a graph. We
prove that for any bounded-degree n-vertex graph, the union of two random
spanning trees approximates the expansion of every cut of the graph to within a
factor of O(log n). For the random graph G_{n,p}, for p> c log{n}/n, two
spanning trees give an expander. This is suggested by the case of the complete
graph, where we prove that two random spanning trees give an expander. The
construction of the splicer is elementary -- each spanning tree can be produced
independently using an algorithm by Aldous and Broder: a random walk in the
graph with edges leading to previously unvisited vertices included in the tree.
  A second important application of splicers is to graph sparsification where
the goal is to approximate every cut (and more generally the quadratic form of
the Laplacian) using only a small subgraph of the original graph.
Benczur-Karger as well as Spielman-Srivastava have shown sparsifiers with O(n
log n/eps^2)$ edges that achieve approximation within factors 1+eps and 1-eps.
Their methods, based on independent sampling of edges, need Omega(n log n)
edges to get any approximation (else the subgraph could be disconnected) and
leave open the question of linear-size sparsifiers. Splicers address this
question for random graphs by providing sparsifiers of size O(n) that
approximate every cut to within a factor of O(log n).
