Erdős ProblemsMathematical logic
Erdős Problem 1176
Let be a graph with chromatic number . Is it true that there is a colouring of the edges with many colours such that, in any countable colouring of the vertices, there exists a vertex colour containing all edge colours?
Mathematical statement
Let be a graph with chromatic number . Is it true that there is a colouring of the edges with many colours such that, in any countable colouring of the vertices, there exists a vertex colour containing all edge colours?
A problem of Erdős, Galvin, and Hajnal. The consistency of this was proved by Hajnal and Komjáth.
Statement source: Erdős Problems statement material
Statement terms: Source-specific
Source-specific terms. Therefore does not assert reuse rights beyond attributed display.
Statement artifacts, not proofs
These records expose exact Lean propositions and statement-only wrappers. Defining a proposition does not supply a proof of it. A placeholder-bearing target also contains no proof. Elaboration checks syntax and types; it does not certify that a formalization perfectly captures every nuance of the informal problem.
Pinned Lean formulation 1
erdos_1176
theorem erdos_1176 : answer(sorry) ↔ ∀ {V : Type*} (G : SimpleGraph V), G.chromaticCardinal = aleph 1 → ∃ (EColor : Type) (_ : mk EColor = aleph 1) (c_edge : G.edgeSet → EColor), ∀ (VColor : Type) (_ : mk VColor ≤ aleph 0) (c_vert : V → VColor), ∃ (vc : VColor), ∀ (ec : EColor), ∃ (u v : V) (h : G.Adj u v), c_vert u = vc ∧ c_vert v = vc ∧ c_edge ⟨s(u, v), h⟩ = ec := by sorry- Statement source
- Formal Conjectures
- Lean version
- v4.27.0
- Placeholder
- Present; no proof artifact
- Source evidence
- Pinned source index
- Fidelity review
- Community formulation
References