Strengthening theorems of Dirac and Erdős on disjoint cycles

Henry A. Kierstead, Alexandr V. Kostochka, Andrew McConvey

Published 2016-02-08Version 1

Let $k \ge 3$ be an integer, $H_{k}(G)$ be the set of vertices of degree at least $2k$ in a graph $G$, and $L_{k}(G)$ be the set of vertices of degree at most $2k-2$ in $G$. In 1963, Dirac and Erd\H{o}s proved that $G$ contains $k$ (vertex-)disjoint cycles whenever $|H_{k}(G)| - |L_{k}(G)| \ge k^{2} + 2k - 4$. The main result of this paper is that for $k \ge 2$, every graph $G$ with $|V(G)| \ge 3k$ containing at most $t$ disjoint triangles and with $|H_{k}(G)| - |L_{k}(G)| \ge 2k + t$ contains $k$ disjoint cycles. This yields that if $k \ge 2$ and $|H_{k}(G)| - |L_{k}(G)| \ge 3k$, then $G$ contains $k$ disjoint cycles. This generalizes the Corr\'{a}di-Hajnal Theorem, which states that every graph $G$ with $H_{k}(G) = V(G)$ and $|H_{k}(G)| \ge 3k$ contains $k$ disjoint cycles.