Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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