  As an extension of a classical tree-partition problem, we consider
decompositions of graphs into edge-disjoint (rooted-)trees with an additional
matroid constraint. Specifically, suppose we are given a graph $G=(V,E)$, a
multiset $R=\{r1,..., r_t\}$ of vertices in $V$, and a matroid ${\cal M}$ on
$R$. We prove a necessary and sufficient condition for $G$ to be decomposed
into $t$ edge-disjoint subgraphs $G_1=(V_1,T_1),..., G_t=(V_t,T_t)$ such that
(i) for each $i$, $G_i$ is a tree with $r_i\in V_i$, and (ii) for each $v\in
V$, the multiset $\{r_i\in R\mid v\in V_i\}$ is a base of ${\cal M}$. If ${\cal
M}$ is a free matroid, this is a decomposition into $t$ edge-disjoint spanning
trees; thus, our result is a proper extension of Nash-Williams' tree-partition
theorem.
  Such a matroid constraint is motivated by combinatorial rigidity theory. As a
direct application of our decomposition theorem, we present characterizations
of the infinitesimal rigidity of frameworks with non-generic "boundary", which
extend classical Laman's theorem for generic 2-rigidity of bar-joint frameworks
and Tay's theorem for generic $d$-rigidity of body-bar frameworks.
