The (2k-1)-connected multigraphs with at most k-1 disjoint cycles

Henry A. Kierstead, Alexandr V. Kostochka, Elyse C. Yeager

Research output: Contribution to journalArticlepeer-review


In 1963, Corradi and Hajnal proved that for all k≥1 and n≥3k, every (simple) graph G on n vertices 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, the authors characterized the simple graphs G with minimum degree δ(G)≥2k—1 that do not contain k disjoint cycles. We use this result to answer Dirac's question in full.

Original languageEnglish (US)
Pages (from-to)77-86
Number of pages10
Issue number1
StatePublished - Feb 1 2017


  • 05C15
  • 05C35
  • 05C40

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics


Dive into the research topics of 'The (2k-1)-connected multigraphs with at most k-1 disjoint cycles'. Together they form a unique fingerprint.

Cite this