MathDB
2023 RMM, Problem 6

Source: 2023 RMM, Problem 6

March 4, 2023
graph theoryRMM 2023combinatorics

Problem Statement

Let r,g,br,g,b be non negative integers and Γ\Gamma be a connected graph with r+g+b+1r+g+b+1 vertices. Its edges are colored in red green and blue. It turned out that Γ\Gamma contains
A spanning tree with exactly rr red edges. A spanning tree with exactly gg green edges. A spanning tree with exactly bb blue edges.
Prove that Γ\Gamma contains a spanning tree with exactly rr red edges, gg green edges and bb blue edges.
Back to ProblemsView on AoPS