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!
$\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.