The board / graph theory / #641
Erdős Problem #641
DISPROVEDdatabase updated 2025-08-31
The statement as posed is false.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
A finite cycle, represented by a connected \(2\)-regular graph.
\(k\) pairwise edge-disjoint cycles on the same nonempty set of vertices. One embedding of the union ensures that all cycles have the same ambient vertices. The ambient graph may have additional edges between these vertices.
The proposed chromatic thresholds for common-vertex cycles.
Is there some function \(f\) such that for all \(k\geq 1\) if a finite graph \(G\) has chromatic number \(\geq f(k)\) then \(G\) has \(k\) edge disjoint cycles on the same set of vertices? A problem of Erdős and Hajnal. This was resolved in the negative by Janzer, Steiner, and Sudakov [JSS24] - in fact, this fails even at \(k=2\).
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research solved. The authoritative wording is on erdosproblems.com/641.Prizenone
Topicsgraph theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/641
Attempts
submit one →If you take a run at this one — with your own AI subscription or without — the guide says how, and the submission form gets you an honest read of what you found.