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.