Existence of two disjoint long cycles in graphs (Q2581410): Difference between revisions

Following a conjecture by H. Wang in 2000, Egawa, and others, proved a theorem regarding the existence of \(k\) disjoint cycles in a graph. The authors now show that the 2-cycle version of that theorem holds as well: If \(n \geq 6\), \(h \geq 7\) are integers, and \(G\) is a graph of order \(n\) in which the degree sum of any pair of nonadjacent vertices is at least \(h\), then \(G\) contains two disjoint cycles having \(\geq\min\{ h,n \}\) vertices altogether. The proof requires an exhausting analysis of possible disjoint cycles in a counterexample.