On the maximum number of independent cycles in a graph (Q1301840): Difference between revisions

\textit{K. Corrádi} and \textit{A. Hajnal} [Acta Math. Acad. Sci. Hung. 14, 423-439 (1963.; Zbl 0118.19001)] proved that a graph of order at least \(3k\) with minimum degree \(\geq 2k\) contains \(k\) vertex-disjoint cycles. In 1989, \textit{D. Justesen} [Ann. Discrete Math. 41, 299-305 (1989; Zbl 0673.05065)] improved this theorem by relaxing the degree condition to \(d(x)+d(y) \geq 4k\) for every pair of non-adjacent vertices \(x\) and \(y\). This paper sharpens the result by reducing the requirement to \(d(x)+d(y) \geq 4k-1\).