# Proof of lemma involving edge-disjoint spanning trees and graph partitions

I have been given the following statement in my lecture notes but it is left without proof.

For every graph $G$ with edges colored with red, blue and green:

The graph $G$ has edge-disjoint spanning trees $T_1$ and $T_2$ such that $T_1$ has only red and green edges and $T_2$ has only blue and green edges if and only if for every partition of the vertices of $G$ there are at least $k −1$ red and green edges with end vertices in different parts, at least $k − 1$ blue and green edges with end vertices in different parts, and at least $2k − 2$ edges in total with end vertices in different parts, where $k$ is the number of parts of the partition.

Can anyone provide any insight into why this holds and provide a detailed proof?

Solution so far:

For the forward direction:

Since $T_1$ and $T_2$ are edge-disjoint spanning trees, it follows that there will be at least $2k-2$ edges with ends in different parts (using a previous theorem presented in my notes).

Since these are spanning, for $T_1$, there must be at least one edge that joins $V_1$ to $V_2$, at least one edge that joins $V_1\cup V_2$ to $V_3$, ... and at least one edge that joins $V_1 \cup\ ... \cup\ V_{k-1}$ to $V_k$, hence there are at least $k-1$ red and green edges with end vertices in different parts.

Similarly, we can argue that there are at least $k-1$ blue and green vertices with end points in different parts, using that $T_2$ is spanning.

So, I think that is the forward direction done, but it sounds very hand wavy and I can't seem to find a nice way to formalise it.

I have got nowhere with the backwards direction at all so far.

So, in brief, I would really appreciate help with proving the second implication and formalising the first. Thank you!

• Any help would be appreciated please! – mathcomp Mar 11 '17 at 14:35
• Did you try to prove it yourself? Which ways did you try? – Smylic Mar 11 '17 at 15:49
• @Smylic I have tried, yes. This is forming part of my revision for my exam in 2 weeks, so I am trying my best to understand everything we have been given :) So, for the forward direction: Since $T_1$ and $T_2$ are edge disjoint spanning trees, it follows that there will be at least $2k-2$ edges with ends in different parts. And since these are spanning, for $T_1$, there must be at least one edge that joins $V_1$ to $V_2$ ... and at least one edge that joins $V_{k-1}$ to $V_k$, hence there are at least $k-1$ red and green edges with end vertices in different parts. [TBC] – mathcomp Mar 11 '17 at 16:44
• @Smylic [CTD] Similarly, we can argue that there are at least $k-1$ blue and green vertices with end points in different parts, using that $T_2$ is spanning. SO i think that is the forward direction done. The only qualms I had with this direction was that it sounds very hand wavy and I can't find a nice way to formalise it. I have got nowhere with the backwards direction at all. SO in brief, I need help with proving the second implication and formalising the first. Thank you! – mathcomp Mar 11 '17 at 16:48
• @Smylic edited the post and corrected some issues with the comments above! – mathcomp Mar 11 '17 at 17:18

$\Rightarrow$: Let $V_1, V_2, \cdots, V_k$ be a partition of the vertex set $V$ for a graph $G = (V, E)$. Because there are two edge-disjoint spanning trees $T_1$ and $T_2$ in $G$, the partition $V_1, V_2, \cdots, V_k$ are also connected using either edges of $T_1$ or edges of $T_2$. Therefore, there are

• at least $2(k-1)$ edges with end vertices in different parts;

• at least $k - 1$ edges colored red and green with end vertices in different parts;

• at least $k - 1$ edges colored blue and green with end vertices in different parts.

$\Leftarrow$: Consider the following counterexample. It satisfies all conditions for all $k$ but does not contain two edge-disjoint spanning trees with specific colors.