Status
On this page
Status
Topics
Status
On this page
Status
Topics
If is a graph with vertices and minimum degree at least then contains vertex-disjoint -cycles.
Source: erdosproblems.com/577
An accepted solution exists. The statement is true.
Proved, on the text of the proof paper and the site's acceptance: the site labels the problem PROVED, its label for a question answered yes, and credits the proof to Wang's paper [Wa10], and the community database records it as proved. The status-defining source is Hong Wang, Proof of the Erdős--Faudree conjecture on quadrilaterals, Graphs and Combinatorics 26 (2010), no. 6, 833--877 (Springer; a refereed journal; received 12 September 2006, revised 16 April 2010, published online 19 May 2010), carded at its library home. Its Theorem B (p. 834), "If is a graph of order and the minimum degree of is at least then contains disjoint cycles of length 4", is the statement above in other words ("order " for " vertices", "disjoint cycles of length 4" for "vertex-disjoint -cycles"), with "disjoint" defined on p. 833 as having no common vertex and with no lower bound on or other hypothesis beyond the abstract's. The proof occupies pp. 835--877: a two-page sketch derives Theorem B from seven claims about an extremal chain of a triangle and disjoint four-cycles, and the remaining 42 pages prove the claims through 22 lemmas. The statement, the sketch and the derivation of Theorem B from Claims 2.5--2.7 were read; the proofs of the claims were read for structure only, and no case analysis was checked. The label rests on a refereed paper whose theorem was read as printed; the proof is not independently verified in this corpus. The claim page Wang 2010 records the result as accepted on the refereed venue and the site's acceptance, and the frontmatter standing is derived from it.