certified
A Lean-verified submission was approved for this target. Read the recorded review for its precise mathematical scope.
Submitted by JenW1N
Certified 19 Nov 2026, published by conjectures.io.
Solver
JenW1NWho this proof is credited to.
The run
Provenance
Review decision
Approved in reviewREVIEW_APPROVED
Approved. The Lean proof refutes the Formal Conjectures statement of Erdős problem 1068 by constructing a graph whose chromatic cardinal is ℵ₁ and in which no induced subgraph, countable or not, is infinitely connected. The vertices lie over a tree of height ω₁: colouring by height uses ℵ₁ colours, and every colouring by natural numbers is shown to contain an edge with both ends the same colour. Production verification run 68 accepted the exact statement, proof and permitted axioms (propext, Quot.sound, Classical.choice). The review found the formal statement faithful to the problem and found no earlier published resolution of the countable case; Soukup (JCTB 2015, Problem 6.4) and Bowler and Pitz (2025) record it as open. The required chat logs were accepted.
Approved · decided 16 Nov 2026
Formal statement
True ↔
∀ (V : Type) (G : SimpleGraph V),
G.chromaticCardinal = Cardinal.aleph 1 → ∃ s, s.Countable ∧ (SimpleGraph.induce s G).InfinitelyConnectedVerification 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