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.



Can we select a rainbow matching if each degree is 6 and each colorclass is a C_6?
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](http://www.renyi.hu/~emlektab/) 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.


