Is there a graph with $ℵ_{2}$ vertices and chromatic number $ℵ_{2}$ such that every subgraph on $ℵ_{1}$ vertices has chromatic number $\leq ℵ_{0}$ ?Is there a graph with $ℵ_{ω + 1}$ vertices and chromatic number $ℵ_{1}$ such that every subgraph on $ℵ_{ω}$ vertices has chromatic number $\leq ℵ_{0}$ ?

Worked, still open.

graph theory · open · formalized (Lean) · 0 attempts

use this record

vela registry pull vfr_37aec80d874a0239

vela reproduce examples/erdos-problems

evidence

unverified AI candidates (2)

gpt-erdos · GPT-5.2 Pro + Deep Research · unverified

Let me phrase your two requirements in the standard “incompactness for chromatic number” language.

candidate solution ↗

llm-hunter · gpt pro 5.2 · unverified

1 LLM attack(s) recorded (gpt pro 5.2); unverified.

candidate solution ↗

formal

AMS 5 · open (literature)

theorem erdos_918.parts.i :
    answer(sorry) ↔ ∃ (V : Type u) (G : SimpleGraph V), #V = ℵ_ 2 ∧ G.chromaticCardinal = ℵ_ 2 ∧
      ∀ (W : Set V) (_ : #W = ℵ₁), (G.induce W).chromaticCardinal ≤ ℵ₀

formal-conjectures/918.lean ↗

status

open

evidence

formal

status

Search Vela