MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $G=(X,Y,E)$ be an $r$-regular bipartite graph where $|X|=|Y|$ . Let $\phi$ an automorphism of $G$ with $\phi(X) = Y$ and $\phi \circ \phi = id$, and let $\psi$ be the mapping induced by $\phi$ on the edges of $G$.

Does $G$ have a matching $M$ such that $\psi(M) \cap M = \emptyset$ ? If so, how many of them it takes to cover the edges of $G$?

share|cite|improve this question
Do you want $r \geq 2$? Otherwise take $G$ to be a single matching with the `edge endpoint reversing' automorphism. – Michael Albert May 22 '12 at 1:55
Also, is $M$ required to be a perfect matching? There are none if $|X|$ is odd. – Brendan McKay May 22 '12 at 2:00
The phrasing says "homework". Voting to close. – Igor Rivin May 22 '12 at 2:03
$r \geq 3$ and $M$ is indeed a perfect matching. @Igor Rivin this is not a Homowork. I am interested in 1-factorizations of bipartite regular graphs when extra conditions on the graphs are imposed. – hbm May 22 '12 at 16:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.