An Algorithmic Answer to the Ore-Type Version of Dirac’s Question on Disjoint Cycles

Corrádi and Hajnal in 1963 proved the following theorem on the NP-complete problem on the existence of k disjoint cycles in an n-vertex graph G: For all k ≥ 1 and n ≥ 3k, every (simple) n-vertex graph G with minimum degree δ(G) ≥ 2k contains k disjoint cycles. The same year, Dirac described the 3-connected multigraphs not containing two disjoint cycles and asked the more general question: Which (2k − 1)-connected multigraphs do not contain k disjoint cycles? Recently, Kierstead, Kostochka, and Yeager resolved this question. In this paper, we sharpen this result by presenting a description that can be checked in polynomial time of all multigraphs G with no k disjoint cycles for which the underlying simple graph G ̲ $$ \underline {G}$$ satisfies the following Ore-type condition: d G ̲ ( v ) + d G ̲ ( u ) ≥ 4 k − 3 $$d_{ \underline {G}}(v)+d_{ \underline {G}}(u)\geq 4k-3$$ for all nonadjacent u, v ∈ V (G).