# special 1-factorization of regular bipartite graphs

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$ always have a 1-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?

-
Is there always a 1-factorization of such a graph, even without the extra requirement? –  Felix Goldberg Jul 23 '14 at 14:14

Labelling $X=\{1,\dots,n \}$ and $Y=\{1',\dots,n' \}$ then wlog $M=\{11',...,nn' \}$. So the problem can equivalently be stated on a $K_n$, because each $M \cup M_i$ yields a 2-factor of $K_n$ by "projection" (imagine $X$ and $Y$ as top and bottom of a regular prism) and by the $C_4$ condition each edge is used exactly once. Orientation of the cycles doesn't matter, and so the question is equivalent to asking if $K_n$ can be decomposed into $k$ edge-disjoint Hamiltonian cycles. The answer is yes, trivially if $n$ is prime, otherwise see e.g. here for some references.