Erdős Problem 128
Let G be a graph with n vertices such that every induced subgraph on ≥ vertices has more than edges. Must G contain a triangle?
Mathematical statement
Let G be a graph with n vertices such that every induced subgraph on ≥ vertices has more than edges. Must G contain a triangle?
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_128
theorem erdos_128 : answer(sorry) ↔ ∀ (V : Type) [Fintype V] (G : SimpleGraph V), (∀ V' : Set V, 2 * V'.ncard + 1 ≥ Fintype.card V → 50 * (G.induce V').edgeSet.ncard > Fintype.card V ^ 2) → ¬ G.CliqueFree 3 := 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