Combinatorics
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.
Formal statement
Proof target
import FormalConjectures.ErdosProblems.«108»
import TaskSupport
namespace Bounty
theorem target : fcTypeOfName% "Erdos108.erdos_108" := by
sorry
end Bounty
Original conjecture (Lean type)
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 ≥ ↑kOriginal conjecture source: FormalConjectures/ErdosProblems/108.lean
References
Something wrong with this formalization?
A statement that does not faithfully capture the original conjecture is the one real risk here, so we would rather hear about it early - before someone spends weeks on it.
Our channel is in the Bittensor Discord server. Join the server first, then open the channel to send your report.
1 piece · 35 lemmas
Individual lemmas, special cases and supporting work, shown in their original scope.
8 Sept 2026
Erdős 108: the case k = 2 proved outright, with the exact threshold f(2,r) = r
5FqLp5…FfZZiK · 35 lemmas