certified
The conjecture is false. There are finite graphs with arbitrarily high chromatic number whose subgraphs of girth at least five need at most six colours. This refutes the proposed bound at r = 5 and k = 7.
Submitted by JenW1N
The PDF is a working mathematical exposition. Lean verification applies to the formal source, not the prose.
Certified 17 Sept 2026, published by conjectures.io.
Review decision
Approved in reviewREVIEW_APPROVED
Erdős 108, refutation: APPROVED / REVIEW_APPROVED, policy v3. Submission accepted 2026-09-15 21:05:40.257294+00:00. The exact accepted counterexample proof and task passed production verification. The proof produces finite graphs of arbitrarily large chromatic number whose girth-at-least-five subgraphs have chromatic number at most six, refuting the universal conjecture at r=5 and k=7. It does not exploit an infinite-graph convention. No material formalization defect, earlier eligible target holder, or qualifying prior exact-target solution was established. An unidentified reference to an attachment is insufficient evidence for disqualification. Approved for the full locked bounty of 3,818.183876164 Alpha; no formalization-defect award applies. Two independent agent assessments, covering formal semantics/integrity and prior-source eligibility, agree with this outcome; no material disagreement required resolution. They used separate contexts of the same model family. No fresh Lean replay was performed. Sources: https://www.erdosproblems.com/108. The miner may request reconsideration from the review team, citing submission 8c083793-9c3c-4960-8a23-869e54fcb584 and providing contrary evidence.
Approved · decided 16 Sept 2026
Formal statement
True ↔
∀ r ≥ 4,
∀ k ≥ 2,
∃ f,
∀ (V : Type u) (G : SimpleGraph V),
Nonempty V → ↑f ≤ G.chromaticNumber → ∃ H, H.coe.girth ≥ r ∧ H.coe.chromaticNumber ≥ ↑kVerification report
Every box below had to hold before the proof counted. They are grouped in the order the verifier reaches them.
Manifest valid — Passed
The task bundle held together: the exact file set, a strict manifest, and every trusted hash matching the bytes on disk.
Task commitment matches — Passed
The bundle digest the submission committed to is the digest of the bundle that was actually verified.
Production task — Passed
The task came from the production pool rather than a test fixture.
Trusted file hashes match — Passed
The pinned dependencies agree across the manifest, the lockfile and the checkout, down to the same Formal Conjectures commit.
Submission policy respected — Passed
The submitted source passed the static scan: no imports, no axiom declarations, no sorry, no native_decide, no unsafe options.
Production sandbox — Passed
The run happened under real isolation, Landrun with seccomp, and the sandbox passed its own live self-test before the proof was touched.
Challenge built — Passed
The trusted Challenge.lean, which contains no miner code, compiled on its own.
Source type hash matches — Passed
The source theorem in the compiled environment still hashes to the type recorded in the task, so the statement has not drifted upstream.
Solution built — Passed
The submitted Solution.lean compiled.
Statement unchanged — Passed
The theorem the proof establishes has exactly the same canonical type as the task's target - it was not weakened or restated.
Only permitted axioms — Passed
The transitive axiom closure of the proof stays inside the axioms this task permits.
Lean kernel accepted — Passed
The Lean kernel replayed the proof and accepted it.
Nanoda accepted — Not run
A second kernel, written independently of Lean's, also accepted the proof.
One kernel, not two
This task does not require a second, independent kernel, so Nanoda was not run. The verdict rests on a single kernel implementation.
Theorems established
Stage COMPLETED · Axioms permitted: propext, Quot.sound, Classical.choice