1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

As $V(G)$ is partitioned into $n$ parts $V_1,\dots,V_n$, for each spanning tree $T_i$ $(i=1,\dots,k)$, we contract $V_1,\dots,V_n$ one by one, denote it as $\tilde{T_i}=T_i/V_1/\dots/V_n$. Note that $\tilde{T_i}$ is also a connected spanning graph with the vertex set $\{V_1,\dots,V_n\}$, hence $\tilde{T_i}$ has at least $n-1$ edges. On the other hand, edges of $\tilde{T_i}$ can be (naturally) mapped injectively to edges of $T_i$, hence $T_i$ has at least $n-1$ edges. As there are $k$ many edge-disjoint spanning trees, we have at least $k(n-1)$ edges in $G$.

$\endgroup$

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.