I have the problem:
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)$.
I see that since there are $k$ edge-disjoint trees and each spanning tree has $n-1$ edges then there are $k(n-1)$ edges in the graph, but how do I show that all of these edges are in different parts of the partition?