  We study a natural problem in graph sparsification, the Spanning Tree
Congestion (\STC) problem. Informally, the \STC problem seeks a spanning tree
with no tree-edge \emph{routing} too many of the original edges. The root of
this problem dates back to at least 30 years ago, motivated by applications in
network design, parallel computing and circuit design. Variants of the problem
have also seen algorithmic applications as a preprocessing step of several
important graph algorithms.
  For any general connected graph with $n$ vertices and $m$ edges, we show that
its STC is at most $\mathcal{O}(\sqrt{mn})$, which is asymptotically optimal
since we also demonstrate graphs with STC at least $\Omega(\sqrt{mn})$. We
present a polynomial-time algorithm which computes a spanning tree with
congestion $\mathcal{O}(\sqrt{mn}\cdot \log n)$. We also present another
algorithm for computing a spanning tree with congestion
$\mathcal{O}(\sqrt{mn})$; this algorithm runs in sub-exponential time when $m =
\omega(n \log^2 n)$.
  For achieving the above results, an important intermediate theorem is
\emph{generalized Gy\H{o}ri-Lov\'{a}sz theorem}, for which Chen et al. gave a
non-constructive proof. We give the first elementary and constructive proof by
providing a local search algorithm with running time $\mathcal{O}^*\left( 4^n
\right)$, which is a key ingredient of the above-mentioned sub-exponential time
algorithm. We discuss a few consequences of the theorem concerning graph
partitioning, which might be of independent interest.
  We also show that for any graph which satisfies certain \emph{expanding
properties}, its STC is at most $\mathcal{O}(n)$, and a corresponding spanning
tree can be computed in polynomial time. We then use this to show that a random
graph has STC $\Theta(n)$ with high probability.
