I have the following problem. It isn't homework--it's additional work I want to do to further grasp the material in my Combinatorics class.
Show that if a graph $G$ contains $k$ edge-disjoint spanning trees, then for each partition ($V_1$, $V_2$, ..., $V_n$) of $V(G)$, the number of edges of $G$ which have ends in different parts of the partition is at least $k(n-1)$.
For each spanning tree (and due to its definition) there must be (at least) an edge connecting $V_1$ to some $V_j$ with $j\ne1$. Without loss of generality you can assume $j=2$. But now there must be some edge connecting $V_1\cup V_2$ to some $V_j$ with $j\notin\{1,2\}$, again assume $k=3$. You can go on with this process until you have all the $V_i$s connected (I'm lazy and will let the complete rigorous induction for you).
At the end you have $n-1$ edges for each spanning tree, and as no two spanning trees share an edge you can be sure that they are all different. Finally, as there are $k$ spanning trees you have that the number of edges of $G$ which have ends in different parts of the partition is at least $k(n-1)$.