2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Any help would be appreciated please! $\endgroup$ – mathcomp Mar 11 '17 at 14:35
  • $\begingroup$ Did you try to prove it yourself? Which ways did you try? $\endgroup$ – Smylic Mar 11 '17 at 15:49
  • $\begingroup$ @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] $\endgroup$ – mathcomp Mar 11 '17 at 16:44
  • $\begingroup$ @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! $\endgroup$ – mathcomp Mar 11 '17 at 16:48
  • 1
    $\begingroup$ @Smylic edited the post and corrected some issues with the comments above! $\endgroup$ – mathcomp Mar 11 '17 at 17:18
2
$\begingroup$

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

enter image description here

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