Documentation

FormalConjectures.ErdosProblems.«128»

Erdős Problem 128 #

Reference: erdosproblems.com/128

theorem Erdos128.erdos_128 :
sorry ∀ (V : Type) [inst : Fintype V] (G : SimpleGraph V) (V' : Set V), 2 * V'.ncard + 1 Fintype.card V50 * (SimpleGraph.induce V' G).edgeSet.ncard > Fintype.card V ^ 2¬G.CliqueFree 3

Let G be a graph with n vertices such that every subgraph on ≥ $n/2$ vertices has more than $n^2/50$ edges. Must G contain a triangle?