let $T_r$ be the graph obtained by deleting from the spanning tree with r red edges the non-red edges. Define analogously $T_g$ and $T_b$. Consider the graph G obtained from the union of $T_r$, $T_g$ and $T_b$, G has r red edges, g green edges and b blue edges. Lemma 1: in G there is no monochromatic cycle. Proof: otherwise there would be a cycle in one of the spanning trees. Lemma 2: if we take the vertices of a connected component C of G there are at least 2 edges in $\Gamma$ of different colors going out from C. Proof: assume there are only edges of one color (wlog) r going out of C, then in the spanning tree with r red edges C is disconnected wich is absurd (note that this proof works alse for the union of vertices of more connected components of G). Now the following algorithm turns G in the desired spanning tree: choose a connected component C of G with a cycle (if there is none then G is a tree), in this cycle there are at least edges of 2 different colors and moreover there are at least edges of 2 different colors in $\Gamma$ connecting C to another set of vertices wich is a connected component in G, so we can replace one edge in the cycle with another edge of the same color connecting C to another connected components of G. In this way the number of connected components decrease, the number of edges of each color is constant and Lemma 1 and 2 are still true.

Alkpolax wrote: let $T_r$ be the graph obtained by deleting from the spanning tree with r red edges the non-red edges. Define analogously $T_g$ and $T_b$. Consider the graph G obtained from the union of $T_r$, $T_g$ and $T_b$, G has r red edges, g green edges and b blue edges. Lemma 1: in G there is no monochromatic cycle. Proof: otherwise there would be a cycle in one of the spanning trees. Lemma 2: if we take the vertices of a connected component C of G there are at least 2 edges in $\Gamma$ of different colors going out from C. Proof: assume there are only edges of one color (wlog) r going out of C, then in the spanning tree with r red edges C is disconnected wich is absurd (note that this proof works alse for the union of vertices of more connected components of G). Now the following algorithm turns G in the desired spanning tree: choose a connected component C of G with a cycle (if there is none then G is a tree), in this cycle there are at least edges of 2 different colors and moreover there are at least edges of 2 different colors in $\Gamma$ connecting C to another set of vertices wich is a connected component in G, so we can replace one edge in the cycle with another edge of the same color connecting C to another connected components of G. In this way the number of connected components decrease, the number of edges of each color is constant and Lemma 1 and 2 are still true. Lemma 2 doesn't have to stay true.

gvole wrote: Lemma 2 doesn't have to stay true. As far as I understand, any "cross" edge (between two connected components) later will have to be one among the initial ones, because you're only merging components and not affecting the edges of $G$. So Lemma 2 does seem to stay true?

L567 wrote: gvole wrote: Lemma 2 doesn't have to stay true. As far as I understand, any "cross" edge (between two connected components) later will have to be one among the initial ones, because you're only merging components and not affecting the edges of $G$. So Lemma 2 does seem to stay true? What if all bridges coming out of a some two components are red except for one which is blue and the process draws that blue edge?

I believe these claims and ideas lead to the solution. However writing it up would take a while. 1. You can safely remove edges so that there is no cycle of the same color 2. Using 1. and the problem statement prove that you can select R red edges and B blue edges so that there is no cycle (do the same for each of the other pairs) 3. Now call a set of R red edges good if you can finish the tree by only adding green or blue edges. Prove that there exist good set of R red edges in addition to at least B blue edges and G green edges such that there is no cycle of colors only green and red or blue and red. Call this set or red edges M. Now add some blue and green edges so that the graph becomes a tree (possible since M is a good set). 4. WLOG there exist more green edges that G and less blue edges than B. Prove that you can add a blue edge so that it doesn’t create a cycle of colors only red and blue. This finishes the problem since the cycle cannot only be blue by 1. Hence it has a green edge that we can remove. Do this algorithm until you are left with the desired graph.

gvole wrote: What if all bridges coming out of a some two components are red except for one which is blue and the process draws that blue edge? You're right, but I think the solution can be fixed by improving Lemma 2 to (as mentioned in the proof): For every (proper) subset of the connected components, there exist edges of at least two different colors exiting it.

Let $S$ be the set of pairs $(r_0,g_0,b_0)$ where there exists a spanning tree with $r_0,g_0,b_0$ red,green,blue edges respectively. It suffices to prove that for $x>x',y<y',z\le z'$ such that $(x,y,z),(x',y',z')\in S$, we have $(x-1,y+1,z)\in S$. Let the trees corresponding to these numbers $T,T'$. Suppose that we cannot replace a red edge in $T$ with a green one in $T'$,still forming a tree. That is to say, the green edges in $T'$ connects vertices only in the connected components in $T$ removing red edges. Now since $y'+z'>y+z$, there exists a blue edge in $T'$ which can replace a red edge in $T$ still forming a tree, say $T''$. Now it suffices to replace a blue edge in $T''$ with a green one in $T'$,still forming a tree. This is true since blue edges in $T'$ can only connect vertices already connected if only preserving blue edges in $T$,contradicting $y'>y$.

This is almost certainly massive overkill, but it hits way too close to my area of research for me to pass this up.

UPDATE (3/10/2023): The (*) statement in the above solution turns out to be not so easy to prove. There is a sketch in #15 and #17 that fixes this issue, but here's another overkill to prove (*) that I find more satisfying:

@above I don't consider matroid overkilling these problems since they are matroid problems themselfes(:

Here is my very short solution from contest with the finish fixed.

yao981113 wrote: This is almost certainly massive overkill, but it hits way too close to my area of research for me to pass this up.

Why all lattice points inside the projection correspond to the vertices? It seems to be the crucial fact, which must use which specific projection do we consider.

Here is a matroid proof (but without matroid polytope). Let $E$ be the set of all edges. Consider two matroids on $E$: the first matroid $M_1$ is a usual graph circuit matroid (independent sets are forests), in $M_2$ independent sets are those which contain at most $r$ red edges, at most $b$ blue edges, at most $g$ green edges. We need to prove that there exist $W\subset E$ which is independent both in $M_1$ and $M_2$ of size $|W|=r+g+b$. By matroid intersection theorem, it exists if and only if the inequality $f(S):=r_2(S)+r_1(E\setminus S) \geqslant r+g+b$, where $r_i$ denote rank functions of $M_i$, $i=1, 2$, holds for arbitrary $S\subset E$. Let the sets $R_1,B_1,G_1$ denote red, blue, green parts of $S$. If, say, $|R_1|>r$, replace $R_1$ to the set $R$ of all Red edges, $f$ can only decrease. If $|R_1|\le r$, replace $R_1$ to $\emptyset$, again $f$ can only decrease. Do the same with other color. We reduced to the case when $S$ consists of several color classes, like all red edges (then $r_1(E\setminus S) \ge b+ g$ because of $T_r$), or all red and blue edges (then $r_1(E\setminus S) \ge g$ because of $T_g$). Remaining cases $S=\emptyset$, $S=E$ are clear.

Fedor Petrov wrote: Why all lattice points inside the projection correspond to the vertices? It seems to be the crucial fact, which must use which specific projection do we consider. You are right, this is a gap in my solution that I realized after posting but couldn't resolve cleanly. The way I am thinking of fixing it goes roughly like this:

yao981113 wrote: Fedor Petrov wrote: Why all lattice points inside the projection correspond to the vertices? It seems to be the crucial fact, which must use which specific projection do we consider. You are right, this is a gap in my solution that I realized after posting but couldn't resolve cleanly. The way I am thinking of fixing it goes roughly like this:

I am bit confused. Which property of matroids do you use and where in the argument is it used?

Fedor Petrov wrote: I am bit confused. Which property of matroids do you use and where in the argument is it used? I am using the strong exchange property. Here's an example:

Here is an amazing argument by one of the contestants, Pavel Prozorov. It uses the theory of so called real stable polynomials. I briefly recall the main definitions and properties. A polynomial $F(x_1,\ldots,x_n)$ with real coefficients is called real stable, if $F(a_1,\ldots,a_n)\ne 0$ whenever $a_1,\ldots,a_n$ are complex numbers with positive imaginary part. For example, if $n=1$ this just means that all roots of $F$ are real. For a polynomial $F(x_1,\ldots,x_n)$ define its Newton polytope $\mathcal{N}(F)$ as the convex hull of all points $(a_1,\ldots,a_n)$ for which $F$ contains the monomial $x_1^{a_1}\ldots x_n^{a_n}$ with non-zero coefficient. The first main fact is Theorem 1. If $F$ is a real stable polynomial with non-negative coefficients, and $(a_1,\ldots,a_n)\in \mathcal{N}(F)$ is an integer point, then $F$ contains the monomial $x_1^{a_1}\ldots x_n^{a_n}$ with non-zero coefficient. Another fact concerns spanning trees. For a connected graph $G=(V,E)$ (loops and multiple edges allowed) take a variable $x_e$ for each edge $e\in E$ and consider the sum $F_G:=\sum_T \prod_{e\in T} x_e$ over all spanning trees $T$ in $G$. Theorem 2. $F_G$ is real stable. Apply Theorem 2 for our graph. Choose three variables $y_r,y_g,y_b$ and replace all $x_e$ for red edges $e$ to $y_r$ etc. You get a polynomial $H(y_r,y_g,y_b)$ which is still real stable (that follows from the definition and real stability of $F_G$). Thus, using Theorem 1, we see that it suffices to prove that the point $(r,g,b)$ belongs to the Newton polytope $\mathcal{N}(H)$. Assume the contrary, then there exists a plane through $(r,g,b)$ such that the whole $\mathcal{N}(H)$ is on one side of it. Say, $\lambda_r(t_r-r)+\lambda_g(t_g-g)+\lambda_b(t_b-b)>0$ for every monomial $y_r^{t_r}y_g^{t_g}y_b^{t_b}$ in $H$ --- in other words, for every spanning tree of $G$, where $t_r,t_g,t_b$ denote the number of its red, green, blue edges respectively. Since $t_r+t_b+t_g=r+g+b$, we may replace $(\lambda_r,\lambda_g,\lambda_b)$ by $(\lambda_r+c,\lambda_g+c,\lambda_b+c)$ for arbitrary constant $c$. Without loss of generality $\lambda_r\geqslant \lambda_g\geqslant \lambda_b$. Choose $c=-\lambda_g$. Now $\lambda_g=0$, $\lambda_r\geqslant 0$, $\lambda_b\leqslant 0$, and it suffices to find a spanning tree such that $t_b\geqslant b$, $t_r\leqslant r$ to get a contradiction. Consider the graph formed by blue edges and its maximal forest. It contains at least $b$ edges because of the tree $T_b$. The red and green edges of $T_r$ are enough to join all the components of this forrest, so do this and we get a spanning tree with at least $b$ blue and at most $r$ red edges. Theorem 2 may be found here https://people.math.harvard.edu/theses/senior/mckenzie/mckenzie.pdf (Proposition 1.1) Theorem 1 follows from Theorem 2.7 here https://arxiv.org/pdf/2006.16847.pdf

yao981113 wrote: Fedor Petrov wrote: I am bit confused. Which property of matroids do you use and where in the argument is it used? I am using the strong exchange property. Here's an example:

Well, but for the spanning trees the strong exchange property is easy without matroids: if $uv=e\in T_1\setminus T_2$, consider the path between $u,v$ in $T_2$, it must contain an edges which joins two components of $T_1-e$, this is an appropriate exchange edge for $e$.

That's why it's an overkill :p

Some people thought this was kind of boring but I liked it. Let $R$ be a spanning tree with exactly $r$ red edges, and define $G$ and $B$ similarly. If there exists any tree that also contains the correct amount of edges of another color (for example $R$ containing exactly $g$ green colors) then we are done. Thus suppose that no such tree exists. I claim that there exists some pair of colors such that one of the corresponding trees has "too many" edges of the third color while the other has "too little"—for example, if $R$ had $>b$ blue edges and $G$ had $<b$ then red and green would work. Indeed, if such a pair does not exist, WLOG let $R$ have $>b$ blue edges, so $G$ has $>b$ blue edges as well. Then it must have $<r$ red edges, otherwise it has more than $r+g+b$ edges, so $B$ has $<r$ red edges as well. Then $B$ has $>g$ green edges, otherwise it also has more than $r+g+b$ edges, so $R$ has $>g$ green edges, but then it has more than $r+g+b$ edges total. Thus such a pair exists, so WLOG suppose that it is red and green, and additionally that $R$ has more than $b$ blue edges (so $G$ has less than $b$). Repeatedly apply the following process: Suppose that there is some blue edge $e$ in $R$ which is not in $G$. If adding $e$ to $G$ forms some cycle $C \cup \{e\}$, then there must be some edge $e' \in C$ which isn't in $R$, else $C \cup \{e\}$ is a cycle in $R$, which is prohibited. If $e'$ is blue then remove $e$ from $R$ and add $e'$ If $e'$ is green then do the same thing If $e'$ is red then remove $e'$ from $G$ and add $e$ It is clear that each operation will preserve the number of red edges in $R$ and the number of green edges in $G$, and moreover both will evidently still be spanning trees of $\Gamma$. Furthermore, the number of edges in $R \cap G$ increases each time this operation is performed, but it also must be bounded by $r+g+b$, so this process will eventually terminate. When this process does terminate, every blue edge in $R$ must also be in $G$, so $G$ has at least as many blue edges as $R$. Observe that the operation either doesn't change the number of blue edges in $R$ or decreases it by $1$, and likewise doesn't change the number of blue edges in $G$ or increases it by $1$. Thus if $R$ has at most $b$ blue edges when this algorithm terminates, at some point it must have had exactly $b$ blue edges by "discrete continuity". At that point, it had $r$ red edges and $b$ blue edges, so it must have had $g$ green edges, since the total number of edges is always $r+g+b$. Otherwise, $G$ also has more than $b$ blue edges when the algorithm terminates, so at some point it must have had exactly $b$ blue edges for the same reason; at that point it must also have had exactly $r$ red edges. Either way, at some point we will have some spanning tree of $\Gamma$ with exactly $r$ red edges, $g$ green edges, and $b$ blue edges, which is the desired result. $\blacksquare$

Solved with eisirrational, goodbear, nukelauncher, and Th3Numb3rThr33. Let the three spanning trees be \(T_R\), \(T_G\), \(T_B\), respectively. Let \(\omega\) be the graph formed by taking the \(r\) red edges \(T_R\), the \(g\) green edges in \(T_G\), and the \(b\) blue edges in \(T_B\). Say that an outside edge is an edge in \(\Gamma\) that, if added to \(\omega\), would connect two connected components of \(\omega\). While there is an outside edge \(e\) and there is a cycle containing an edge \(f\) of the same color, we delete \(f\) and add \(e\) to \(\omega\). This process decreases the number of connected components, so it terminates. After this, \(\omega\) still has \(r\) red edges, \(g\) green edges, and \(b\) blue edges. We will show \(\omega\) is a tree. Assume for contradiction \(\omega\) is not a tree, ergo it is not connected. Since our process never creates a cycle, all cycles contain at least two colors (otherwise one of the original three spanning trees contains a cycle). Since \(\omega\) is disconnected, outside edges still exist, but no cycle in \(\omega\) may share a color with an outside edge. Hence, all outside edges are the same color (without loss of generality, green), and all cycles contain edges of the other two colors. Since \(T_G\) is connected, it must contain an outside edge. Since each outside edge is green, this means \(\omega\) started with this outside edge. But our process never increases connected components, so this outside edge is still in \(\omega\), which is absurd.

Fedor Petrov wrote: Here is a matroid proof (but without matroid polytope). Let $E$ be the set of all edges. Consider two matroids on $E$: the first matroid $M_1$ is a usual graph circuit matroid (independent sets are forests), in $M_2$ independent sets are those which contain at most $r$ red edges, at most $b$ blue edges, at most $g$ green edges. We need to prove that there exist $W\subset E$ which is independent both in $M_1$ and $M_2$ of size $|W|=r+g+b$. By matroid intersection theorem, it exists if and only if the inequality $f(S):=r_2(S)+r_1(E\setminus S) \geqslant r+g+b$, where $r_i$ denote rank functions of $M_i$, $i=1, 2$, holds for arbitrary $S\subset E$. Let the sets $R_1,B_1,G_1$ denote red, blue, green parts of $S$. If, say, $|R_1|>r$, replace $R_1$ to the set $R$ of all Red edges, $f$ can only decrease. If $|R_1|\le r$, replace $R_1$ to $\emptyset$, again $f$ can only decrease. Do the same with other color. We reduced to the case when $S$ consists of several color classes, like all red edges (then $r_1(E\setminus S) \ge b+ g$ because of $T_r$), or all red and blue edges (then $r_1(E\setminus S) \ge g$ because of $T_g$). Remaining cases $S=\emptyset$, $S=E$ are clear. I was about to comment a matroid solution and you beat me to it , guess the author first approached this with matroids and then found an elementary solution.

Nguyenhuyhoang wrote: Fedor Petrov wrote: Here is a matroid proof (but without matroid polytope). Let $E$ be the set of all edges. Consider two matroids on $E$: the first matroid $M_1$ is a usual graph circuit matroid (independent sets are forests), in $M_2$ independent sets are those which contain at most $r$ red edges, at most $b$ blue edges, at most $g$ green edges. We need to prove that there exist $W\subset E$ which is independent both in $M_1$ and $M_2$ of size $|W|=r+g+b$. By matroid intersection theorem, it exists if and only if the inequality $f(S):=r_2(S)+r_1(E\setminus S) \geqslant r+g+b$, where $r_i$ denote rank functions of $M_i$, $i=1, 2$, holds for arbitrary $S\subset E$. Let the sets $R_1,B_1,G_1$ denote red, blue, green parts of $S$. If, say, $|R_1|>r$, replace $R_1$ to the set $R$ of all Red edges, $f$ can only decrease. If $|R_1|\le r$, replace $R_1$ to $\emptyset$, again $f$ can only decrease. Do the same with other color. We reduced to the case when $S$ consists of several color classes, like all red edges (then $r_1(E\setminus S) \ge b+ g$ because of $T_r$), or all red and blue edges (then $r_1(E\setminus S) \ge g$ because of $T_g$). Remaining cases $S=\emptyset$, $S=E$ are clear. I was about to comment a matroid solution and you beat me to it , guess the author first approached this with matroids and then found an elementary solution. For what it worth, I realized that an even simpler approach is to apply Rado's independent transversal theorem (Hall marriage theorem for matroids) to such a multi-family of sets: $r$ sets consisting of red edges, $b$ sets consisting of blue edges, $g$ sets consisting of green edges.

Nguyenhuyhoang wrote: Fedor Petrov wrote: Here is a matroid proof (but without matroid polytope). Let $E$ be the set of all edges. Consider two matroids on $E$: the first matroid $M_1$ is a usual graph circuit matroid (independent sets are forests), in $M_2$ independent sets are those which contain at most $r$ red edges, at most $b$ blue edges, at most $g$ green edges. We need to prove that there exist $W\subset E$ which is independent both in $M_1$ and $M_2$ of size $|W|=r+g+b$. By matroid intersection theorem, it exists if and only if the inequality $f(S):=r_2(S)+r_1(E\setminus S) \geqslant r+g+b$, where $r_i$ denote rank functions of $M_i$, $i=1, 2$, holds for arbitrary $S\subset E$. Let the sets $R_1,B_1,G_1$ denote red, blue, green parts of $S$. If, say, $|R_1|>r$, replace $R_1$ to the set $R$ of all Red edges, $f$ can only decrease. If $|R_1|\le r$, replace $R_1$ to $\emptyset$, again $f$ can only decrease. Do the same with other color. We reduced to the case when $S$ consists of several color classes, like all red edges (then $r_1(E\setminus S) \ge b+ g$ because of $T_r$), or all red and blue edges (then $r_1(E\setminus S) \ge g$ because of $T_g$). Remaining cases $S=\emptyset$, $S=E$ are clear. I was about to comment a matroid solution and you beat me to it , guess the author first approached this with matroids and then found an elementary solution. As far as I know, this is not the case. Some people, including Vasya Mokin, have such a strong mathematical intuition that the questions they ask appear to have unexpected underlying science behind.

Here is my solution: https://calimath.org/pdf/RMM2023-6.pdf And I uploaded the solution with motivation to: https://youtu.be/aA3eBFP4G3Q

A remark: In #10 the act of projecting the matroid polytope to $\mathbb{R}^3$ is the same as the act of renaming variables and taking the Newton polytope in #18. I sincerely hope there is some really deep connections.

Let, $T_r$ be the spanning tree with $r$ red edges and define $T_g, T_b$ similarly. Now it's easy to see that if none of these satisfies the condition then there is a colour (WLOG blue) s.t. $T_r$ have more than $b$ blue edges (less than $g$ green edges) and $T_g$ has less than $b$ blue edges (more than $r$ red edges). Now, we transform a tree $T$ from $T_r$ to $T_g$ in this way, Start with $T = T_r$ At each step add a green edge from $T_g$ that is not in $T$. And from the newly created cycle, remove one edge not in $T_g$. Notice that on the resulting graph (let's call it $T_{res}$) the number of green edges is $g$ and all of them are from $T_g$, and in each step the number of blue and red edges are non-increasing. So, the number of red edges is $\leq r$ thus number of blue edge is $\geq b$. Now, $T_g$ has number of blue edges $< b$ so, if we apply this, Start with $T = T_{g}$ At each step add a blue edge from $T_{res}$ that is not in $T$. And from the newly created cycle, remove one edge not in $T_{res}$. Clearly, at the end of this process, we will have the number of blue edges $\geq b$ because the final graph will have all the blue edges from $T_{res}$. But notice that we are not changing the number of green edges (because $T_{res}$ and $T_g$ have the same set of green edges). So at some point, $T$ will have $g$ green edges and $b$ blue edges and thus also $r$ red edges. So we are done. $\blacksquare$

Use a greedy-type algorithm: start with a subgraph $H$ of $G$ with the $r$ red edges from the spanning tree and similar for the other colors. Consider the following operation, where we remove one edge of a color $c$ in a cycle in $H$ and introduce to $H$ an edge of the same color that connects two of its components. Suppose that at some point, this operation can no longer be performed, and furthermore $H$ is not connected. Then $H$ has a cycle $C$; note that $C$ cannot be monochromatic, as $C$ was in the original subgraph and cannot be part of one spanning tree. Thus, this implies that all edges between the connected components of $H$ are of one color $c_1$. On the other hand, consider originally the spanning tree with color $c_1$. As this tree was connected, it must have contained one of these edges with color $c_1$, say $e$; but then $e \in H$, and as the operation cannot disconnect any connected components, it follows that $e$ should still be in $H$, clear contradiction.

Let $T_r, T_g, T_b$ be the spanning trees given in the problem statement. Let $G$ be the union of the red edges in $T_r$, the green edges in $T_g$, and the blue edges in $T_b$. Observe that 1. $G$ has no monochromatic cycles 2. For any partition $V(G) = S_1\sqcup S_2$ such that there is no edge in $G$ between $S_1$ and $S_2$ , there exists an edge in $T_r$ between $S_1$ and $S_2$. In particular, this edge is not red. Note that identical facts hold for the other two colors. Now, consider the following algorithm: Take a cycle $C$ in $G$. Since $C$ is not monochromatic, it contains edges of at least two colors, WLOG red and green. Let $V(G)=S_1\sqcup S_2$ be a partition as in the second fact above. Then there exists a red or green edge between $S_1$ and $S_2$. Add this edge to $G$, and remove an edge of the same color form $C$. Now observe that The algorithm creates no new cycles, so the first fact above remains true Connected components of $G$ are always unions of connected components of the original graph, so the second fact above remains true $G$ always contains exactly $r$ red vertices, $g$ green vertices, and $b$ blue vertices, and the number of connected components decreases by one at each step Simply repeat the algorithm until $G$ is connected, and we have our desired spanning tree.

I have a short solution. Let $T_r$ be the subgraph formed by deleting the non-red edges in the spanning tree with exactly red edges. Define $T_g$ and $T_b$ similarly. Let $H$ be the graph formed by taking the union of the edges of these three graphs. If the resulting graph is a tree, we are done. If not, the graph must be disconnected and have a cycle. Break the cycle by removing an edge of a color, let's say red, and connecting two disconnected components using that red edge. Observe that this process preserves the $r$ red edges, $b$ blue edges and $g$ green edges but it strictly reduces the number of cycles in $H$. We keep on doing this process till we reach a graph with no cycles and has $r+g+b+1-1$ edges which must be a tree. $\blacksquare$