Erdős Problem #739
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: not provable (not automatically the live result).
Subject areas: graph theory, chromatic number.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
For any infinite cardinal m and graph G with chromatic number exactly m, does G contain a (not necessarily induced) subgraph with chromatic number n for every infinite n<m? Erdős #739 is NOT PROVABLE AS A UNIVERSAL ZFC THEOREM if the underlying set-theoretic consistency results are accepted. The maintained source records relative consistency of a negative answer and a positive result under the axiom of constructibility for m=aleph_2 and n=aleph_1. It remains open under the Generalized Continuum Hypothesis in the source, so 'not provable' must not be read as an unconditional ZFC theorem of negation.
A small example
A finite analogy is elementary: the complete graph K_4 has chromatic number four, and contains a triangle K_3 of chromatic number three, as well as an edge K_2. This simple finite monotonicity of chromatic number is NOT a proof that one can realize all intermediate infinite cardinal chromatic numbers in an arbitrary infinite graph; transferring it would ignore the set-theoretic consistency phenomenon.
What is known
Galvin [Ga73] proved a countable-chromatic special result and pointed out that requiring the subgraph to be INDUCED imposes much stronger cardinal-arithmetic consequences. Komjáth [Ko88b], 'Consistency results on infinite graphs', Israel Journal of Mathematics 61 (1988) 285–294, gives a model where a graph of chromatic number aleph_2 has no subgraph of chromatic number aleph_1, under the relative consistency of stated cardinal arithmetic. Shelah [Sh90] proves a positive statement under constructibility. A finite graph search cannot test independence from set theory or forcing arguments. The primary technical model constructions were not independently verified.
GCL's current state
The original authenticated RESULT/1 source return records BOUNDED_TASK_DESIGNED and retains the original mathematical qualifications. This is an editorially reviewed explanatory article in the EC-BULK-005-R9 protected batch, effective only when that exact-hash transaction merges. The corresponding maintained Erdős statement and its bibliography were inspected. This editorial decision does not certify any full original theorem proof, independent external formalization, or Lean kernel check.
Preserved source-review qualifications: komjath 1988 negative in some zfc models; shelah constructibility positive special case; gch general case open. See the immutable 128-case critical review record for the complete source-return caveats.
What remains
ERDOS-739-CONSISTENCY_SCOPE. Read Komjáth 1988 and Shelah 1990 theorems directly, specify their exact background axioms, proper-versus-induced subgraphs, and models. Express a model-indexed implication: existence of a counterexample in a ZFC model refutes ZFC-provability of the universal sentence, under the assumed consistency. No statement that ZFC itself proves failure.
Sources and claim boundaries
Maintained Erdős #739; authenticated GCL source return; Historical full primary proofs have not been independently replayed. No real-browser mathematical rendering, protected batch merge or V2 admission.
Editorial source decision: R9 critical review, REVIEWED as a source-grounded explanation only. All open mathematical questions, primary-proof fidelity obligations, and external formalization caveats remain separate.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2010 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.