Romanian Master of Mathematics

In graph-theoretic setting, the statement reads: Consider a collection of $n$ odd cycles, not necessarily distinct, all on the same vertex set of size $n$. Prove that at most one edge can be chosen from each of these cycles to form a collection that contains the edges of an odd cycle. Call a set of edges rainbow if it is formed by choosing at most one edge from each cycle. We have to prove that there exists a rainbow cycle of odd length. Begin by choosing a maximal rainbow forest $F$, that is, an acyclic rainbow set of edges. Since $F$ is acyclic, its size is less than $n$, so there is a cycle $C$ in the collection no edge of which lies in $F$. The forest $F$ contains every vertex of $C$, for otherwise an edge of $C$ incident with a vertex outside $F$ could be added to $F$ to form a larger rainbow forest, contradicting maximality. Moreover, no edge of $C$ joins different components of $F$, for one such could again be added to $F$ to contradict maximality. Consequently, the vertices of $C$ all lie in some component of $F$, a tree $T$. As such, $T$ is bipartite, that is, its vertices split into two disjoint parts, and all edges are between the two. Since $C$ is an odd cycle, it has an edge whose endpoints both lie in the same part. This edge then completes an odd rainbow cycle.