Skip to content
Cairn Commons
X Sign in
Level A · Machine-checkable Hard Graph theory P-erdos-1175

Erdős Problem #1175

Let κ be an uncountable cardinal. Must there exist a cardinal λ such that every graph with chromatic number λ contains a triangle-free subgraph with chromatic number κ? Shelah proved that a negative answer is consistent when κ = λ = aleph_1 (see erdos_1175.variants.aleph_one).

From the catalogue. Imported from The Formal Conjectures Authors (Google DeepMind and contributors) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim. A Lean proof is checked against the statement below by the Lean kernel; a curator confirms before the problem counts as resolved.

Start working on it Submit a claim Follow
Cite 
@misc{cairn-erdos-1175,
  title        = {Erdős Problem #1175},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/erdos-1175}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-09-29}
}

Also: CITATION.cff · Atom feed of results

Claims
0
Verified
0
Disputed
0
Refuted
0
On the literature board
0

Current state

No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.

The problem

The question

Let be an uncountable cardinal. Must there exist a cardinal such that every graph with chromatic number contains a triangle-free subgraph with chromatic number ?

Shelah proved that a negative answer is consistent when (see erdos_1175.variants.aleph_one).

Formal statement (Lean 4)

From Formal Conjectures, module FormalConjectures.ErdosProblems.«1175». answer(sorry) marks a yes/no question: a proof of the statement on the right of ↔, or of its negation, answers it.

theorem erdos_1175 : answer(sorry) ↔
    ∀ (κ : Cardinal), ℵ₀ < κ →
      ∃ (μ : Cardinal),
        ∀ (V : Type*) (G : SimpleGraph V), G.chromaticCardinal = μ →
          ∃ (H : G.Subgraph), H.coe.CliqueFree 3 ∧ H.coe.chromaticCardinal = κ

What counts as progress

  • A Lean proof of the pinned statement (or of its negation, for a yes/no question) — checked by the Lean kernel against the upstream statement; a curator confirms before the problem is marked resolved.
  • Partial results: special cases, weaker bounds, reductions — as verified claims.
  • Computations and numerical evidence with published code (reproducible).
  • Literature: the problem may have been solved or partly solved already — check erdosproblems.com/1175. Report it as a literature claim.
  • A precise flaw in the formal statement (a misformalisation) — report it upstream too.

Variants

  • erdos_1175.variants.aleph_one — The case κ = λ = aleph_1 of Problem 1175: does every graph with chromatic number aleph_1 contain a triangle-free subgraph with chromatic number aleph_1?
  • erdos_1175.variants.threshold_formulation — Threshold reformulation variant. Replaces chromaticCardinal = λ in the hypothesis of erdos_1175 with λ ≤ chromaticCardinal (a graph of chromatic number ≥ λ has…

References

erdosproblems.com/1175

  • [KoSh88] Komjáth, Péter and Shelah, Saharon, *Forcing constructions for uncountably chromatic graphs*. J. Symbolic Logic (1988), 696--707.

Formalization notes

  • Chromatic cardinal: SimpleGraph.chromaticCardinal is the cardinal-valued chromatic number defined in FormalConjecturesForMathlib. It extends the finite chromaticNumber (which takes values in ℕ∞) to a Cardinal, and is therefore able to distinguish between different infinite chromatic numbers.
  • Triangle-free subgraph: a subgraph H : G.Subgraph is triangle-free when H.coe.CliqueFree 3. This is the standard Mathlib formulation: CliqueFree 3 means the graph has no K₃ as a clique.
  • Subgraph: we use G.Subgraph (an arbitrary subgraph record) rather than an induced subgraph since the problem asks for any subgraph, not just induced ones.

Source and licence

Imported from Formal Conjectures (Erdős problems), commit e6d1743831c2. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.