Decomposition of complete bipartite graphs into paths and cycles

We give conditions for decomposability of the complete bipartite graph K m , n into paths and cycles having k edges. In particular, we find necessary and sufficient conditions for such decomposition in K m , n , when m ≥ k 2 , n ≥ ⌈ k + 1 2 ⌉ for k ≡ 0 ( mod 4 ) and when m , n ≥ 2 k for k ≡ 2 ( mod 4 ) . As a consequence, we show that for nonnegative integers p and q , an even integer k , and odd n with n > 4 k , there exists a decomposition of the complete graph K n into p paths and q cycles both having k edges if and only if k ( p + q ) = n 2 and p ≠ 1 .