On the maximum number of independent cycles in a bipartite graph

Let G = (V-1, V-2; E) be a bipartite graph with \V-1\ = \V-2\ = n greater than or equal to 2k, where k is a positive integer. Suppose that the minimum degree of G is at least k + 1. We show that if n > 2k, then G contains k vertex-disjoint cycles. We also show that if n = 2k, then G contains k - 1 quadrilaterals and a path of order 4 such that all of them are vertex-disjoint. Moreover, the condition on degrees is sharp. We conjecture that when n = 2k, G indeed contains k vertex-disjoint quadrilaterals. (C) 1996 Academic Press, Inc.