Can we select a rainbow matching if each degree is 6 and each colorclass is a C_6? Suppose that we have a 2d-regular graph whose edges are colored such that the edges of each color form a cycle of length 2d. (So if the graph has 2n vertices, then there are n colors.) Is it true that there always is a perfect matching containing one edge of each color?
Remarks. For d=2 there is a simple proof by Zoltan Kiraly who also invented the above formulation of the problem. I even do not know the answer for d=3.
 A: This is a little embarrassing, but it turned out that not even a (non-rainbow) matching is guaranteed to exist. The problem was solved on this workshop by a number of people, presented by Tamas Terpai. They raised the same question for bipartite graphs, for which a matching must always exist.
A: I like this question, so this non-answer is largely intended just to bump it back to the top in the hope that someone else will make something out of it.  Here are some silly comments:


*

*The reason we must have an even number of vertices (i.e., why 2n appears in the question instead of n) is because we are looking for a perfect matching.

*The reason the length of the cycles must be even (i.e., why 2d appears in the question instead of d) is because the degree of each vertex is even: each cycle contributes either 0 or 2 edges to each vertex.

*The cases $k = 0$ and $k = 2d$ of my suggested generalization are trivial.  The case $k = d$ is also easy: from each cycle, take every other edge.  It's also clear that if the result holds for $k = a$ then it also holds for $k = 2d - a$.

*At some point I thought I had come up with a solution for the case $d = 2$, $k = 1$ (i.e., the case domotorp attributes to Z. Kiraly), but I either was mistaken or I have forgotten it.  So, I would be interested in seeing even the proof of that case.

*Assuming we always can make such a choice, is there some more general class of graphs with which we can replace cycles and still have the result be true?

