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$

2 Answers 2

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .