On the Corrádi–Hajnal theorem and a question of Dirac

Abstract In 1963, Corradi and Hajnal proved that for all k ≥ 1 and n ≥ 3 k , every graph G on n vertices with minimum degree δ ( G ) ≥ 2 k contains k disjoint cycles. The bound δ ( G ) ≥ 2 k is sharp. Here we characterize those graphs with δ ( G ) ≥ 2 k − 1 that contain k disjoint cycles. This answers the simple-graph case of Dirac's 1963 question on the characterization of ( 2 k − 1 ) -connected graphs with no k disjoint cycles. Enomoto and Wang refined the Corradi–Hajnal Theorem, proving the following Ore-type version: For all k ≥ 1 and n ≥ 3 k , every graph G on n vertices contains k disjoint cycles, provided that d ( x ) + d ( y ) ≥ 4 k − 1 for all distinct nonadjacent vertices x , y . We refine this further for k ≥ 3 and n ≥ 3 k + 1 : If G is a graph on n vertices such that d ( x ) + d ( y ) ≥ 4 k − 3 for all distinct nonadjacent vertices x , y , then G has k vertex-disjoint cycles if and only if the independence number α ( G ) ≤ n − 2 k and G is not one of two small exceptions in the case k = 3 . We also show how the case k = 2 follows from Lovasz' characterization of multigraphs with no two disjoint cycles.