# 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.

-
And, more generally, can we choose k edges from each cycle in such a way that each vertex is an endpoint of exactly k of the edges? (I've only been able to solve the case d = 1 so far ;) .) –  JBL May 18 '10 at 3:23
This paper seems slightly relevant: combinatorics.org/Volume_17/Abstracts/v17i1n26.html They prove that if every vertex is incident to edges of $d$ distinct colors then there exists a rainbow matching of size at least $\lfloor d/2\rfloor$ (making no assumptions about the structure of the colored edges, unlike in this question). –  JBL May 27 '10 at 13:57
Thanks! Unfortunately in this case d/2 is already guaranteed by a greedy argument... –  domotorp May 27 '10 at 16:20

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.

-
This comment is totally off-topic, but it looks like a great workshop! (I have very fond memories of classes taught by Simonyi and Gyarfas.) –  JBL Jul 31 '10 at 18:22
• 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.