Sign up ×

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.

share|cite|improve this question
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: 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

2 Answers 2

up vote 2 down vote accepted

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.

share|cite|improve this answer
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

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?
share|cite|improve this answer
Make a bipartite graph where on the lower side you have the vertices of the original graph, on the upper two vertices for each colorclass, each being connected to two opposite vertices of the C_4 of that color. This is a 2-regular bipartite graph now and what we need is a perfect matching. – domotorp May 23 '10 at 8:41

Your Answer


