## Abstract

Let k ≥ 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)|≥k^{2}+2k−4. The main result of this article is that for k≥2, every graph G with |V(G)|≥3k containing at most t disjoint triangles and with |H_{k}(G)|−|L_{k}(G)|≥2k + t contains k disjoint cycles. This yields that if |H_{k}(G)|−|L_{k}(G)|≥3k and k≥2, 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)|≥3k contains k disjoint cycles.

Original language | English (US) |
---|---|

Pages (from-to) | 788-802 |

Number of pages | 15 |

Journal | Journal of Graph Theory |

Volume | 85 |

Issue number | 4 |

DOIs | |

State | Published - Aug 2017 |

## Keywords

- disjoint cycles
- disjoint triangles
- minimum degree
- planar graphs

## ASJC Scopus subject areas

- Geometry and Topology