RMM 2023 Problem 6

Let $r, g, b$ be non-negative integers. Let $\Gamma$ be a connected graph on $r+g+b+1$ vertices. The edges of $\Gamma$ are each coloured red, green or blue. It turns out that $\Gamma$ has

• a spanning tree in which exactly $r$ of the edges are red,
• a spanning tree in which exactly $g$ of the edges are green and
• a spanning tree in which exactly $b$ of the edges are blue.

Prove that $\Gamma$ has a spanning tree in which exactly $r$ of the edges are red, exactly $g$ of the edges are green and exactly $b$ of the edges are blue.

Russia, Vasily Mokin