Strengthening theorems of Dirac and Erdős on disjoint cycles

Abstract

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ő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á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.

arXiv comment13 pages