The board / graph theory / #85
Erdős Problem #85
OPENdatabase updated 2026-03-14
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
Let \(f(n)\) be the smallest integer for which every graph on \(n\) vertices with minimal degree \(\geq f(n)\) contains a \(C_4\).
Is it true that, for all large \(n\), \(f(n + 1) \ge f(n)\)?
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open. The authoritative wording is on erdosproblems.com/85.Prizenone
Topicsgraph theory, ramsey theory
Statement in LeanFormal Conjectures
Solution in Leanno
OEISA006672
Original pageerdosproblems.com/85