Erdos-Faber-Lovasz Conjecture
Graph TheorySOLVED
Year
1972
Difficulty
*****
Solved by
Kang, Kelly, Kuhn, Methuku & Osthus (2021)
Statement
The union of n complete graphs sharing at most one vertex each is n-colorable.
About this Problem
Erdos considered this one of his three favorite problems. Proved for sufficiently large n in 2021 after nearly 50 years.
About the Lean 4 Prover
Lean 4 is a theorem prover and programming language. When a proof compiles in Lean, it is mathematically certain to be correct — the type checker verifies every logical step. This is the gold standard for formal verification.
Our platform uses fal.ai serverless compute to run Lean verification, and Gemini to generate proof strategies that are then formally checked. ShinkaEvolve provides the evolutionary backbone for automated mathematical discovery.
Mathematical Art
Generate a unique AI illustration of this problem using fal.ai FLUX.