Skip to content / Đến nội dung
ThichHocToan.com

MathNet 2023-part-01 — 191 problems (EN–VI) Question 132

Math Olympiad Vault · MathNet 2023-part-01 — 191 problems (EN–VI)

Question 132

Let $G$ be a complete bipartite graph with partition sets $A$ and $B$ of sizes $km$ and $kn$, respectively. The edges of $G$ are colored in $k$ colors. Prove that there exists a monochromatic connected component with at least $m+n$ vertices (which means that there exists a color and a set of vertices, such that between any two of them, there is a path consisting of edges only in that color).