The board / graph theory / #595
Erdős Problem #595
OPENdatabase updated 2025-08-31
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).
**Erdős Problem 595 (\\(250)**: Is there an infinite graph \)G\( which contains no \)K_4$ and is not the union of countably many triangle-free graphs? A problem of Erdős and Hajnal [Er87].
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 1 further variant / known partial result in the Lean file. The authoritative wording is on erdosproblems.com/595.Prize$250
Topicsgraph theory, set theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/595
Attempts
submit one →Read our working report →
The live page is OPEN - $250 with 0 claimed proofs, but lists Sam_Petkov as “Currently working on this problem.”
SKIPPED