A sharp Dirac-Erd\H{o}s type bound for large graphs

Let $k\ge 3$ be an integer, $h_k(G)$ be the number of vertices of degree at least $2k$ in a graph $G$, and ${\mathrm{\ell }}_k(G)$ be the number of vertices of degree at most $2k-2$ in $G$. Dirac and Erd\H{o}s proved in 1963 that if $h_k(G)-{\mathrm{\ell }}_k(G)\ge k^2+2k-4$, then $G$ contains $k$ vertex-disjoint cycles. For each $k\ge 2$, they also showed an infinite sequence of graphs $G_k(n)$ with $h_k(G_k(n))-{\mathrm{\ell }}_k(G_k(n))=2k-1$ such that $G_k(n)$ does not have $k$ disjoint cycles. Recently, the authors proved that, for $k\ge 2$, a bound of $3k$ is sufficient to guarantee the existence of $k$ disjoint cycles and presented for every $k$ a graph $G_0(k)$ with $h_k(G_0(k))-{\mathrm{\ell }}_k(G_0(k))=3k-1$ and no $k$ disjoint cycles. The goal of this paper is to refine and sharpen this result: We show that the Dirac-Erd\H{o}s construction is optimal in the sense that for every $k\ge 2$, there are only finitely many graphs $G$ with $h_k(G)-{\mathrm{\ell }}_k(G)\ge 2k$ but no $k$ disjoint cycles. In particular, every graph $G$ with $|V(G)| \geq 19k$and$h_{k}(G) - \ell_{k}(G) \geq 2k$contains$k$ disjoint cycles.