A sharp Dirac-Erdős type bound for large graphs

Abstract

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 ${\ell }_k(G)$ be the number of vertices of degree at most $2k-2$ in $G$. Dirac and Erdős proved in 1963 that if $h_k(G)-{\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))-{\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))-{\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ős construction is optimal in the sense that for every $k\ge 2$, there are only finitely many graphs $G$ with $h_k(G)-{\ell }_k(G)\ge 2k$ but no $k$ disjoint cycles. In particular, every graph $G$ with $|V(G)|\ge 19k$ and $h_k(G)-{\ell }_k(G)\ge 2k$ contains $k$ disjoint cycles.