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

Let $n= 2k+1, |X|=|Y|= n$ and $G= (X, Y, E)$ be a $(k+1)$-regular bipartite graph. Let $M $ be a perfect matching of $G$ having the property that every cycle of size 4 $C_4 $ intersects ` $M$ in at most one edge.

Does $G $ have a factorization ` $ M, M_1, M_2, ...., M_k$ such that:

for all $1\leq i \leq k$ ` $M \cup M_i$ is a Hamiltonian cycle

share|improve this question
add comment

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.