1
$\begingroup$

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)$.

$\endgroup$
0
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ Technically, there need not be an edge going from $V_i$ to $V_{i+1}$. However, there must be an edge going somewhere else. If you're careful not to count these edges twice, there are at least $n-1$ edges and therefore this argument works. $\endgroup$ – Tyler Seacrest Apr 24 '15 at 20:39
  • $\begingroup$ @TylerSeacrest Hum, thanks for pointing out that error! $\endgroup$ – Alvaro Fuentes Apr 24 '15 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.