On the maximum number of independent cycles in a graph Original Research Article

Let G be a graph of order at least 3k, where k is a positive integer. Justesen (Ann. Disc. Math. 41 (1989) 299–306) proved that if d(x)+d(y)⩾4k for every pair of non-adjacent vertices x and y of G, then G contains k vertex-disjoint cycles. This improved the result of Corrádi and Hajnal (Acta Math. Acad. Sci. Hung. 14 (1963) 423–439), who proved the same conclusion provided that the minimum degree of G is at least 2k. In this paper, we strengthen and expand Justesenʹs result, showing that if d(x)+d(y)⩾4k−1 for every pair of non-adjacent vertices x and y of G, then G contains k vertex-disjoint cycles. Moreover, the condition on degrees is sharp.