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?
Best Answer
Conceptual note
First, note that each spanning tree will have $|G|-1$ edges... since $G$ is partitioned into $n$ vertex classes, it is likely that each tree has more than $n-1$ vertices total, i.e. $|G|\geq n$ but could be much much larger than $n$.
Rough idea of solution
Consider any partition of the vertex set $V_1,...,V_{n}$ and let $T_{i}$ be a spanning tree--one of the $k$ edge disjoint spanning trees you are guaranteed to have. Consider only the edges in $T_{i}$ and view the sets $V_{i}$ as a single vertex; say that $V_{i}\sim V_{j}$ if any vertex in $V_{i}$ is adjacent to any vertex in $V_{j}$. Note that since $T_{i}$ is a spanning tree the glob graph you just created is connected. Since the glob graph is on $n$ vertices and is connected it contains at least $n-1$ edges. These edges are precisely those in $T_{i}$ that have endpoints in two different partitions of the vertices. You could have constructed the edge set of your glob graph with any of the $k$ edge-disjoint spanning trees. Thus, you have at least $k(n-1)$ edges with endpoints in two different sets of vertices.