Theorems · Theorem · combinatorics

SimpleGraph.extremalNumber_le_iff

∀ {V : Type u_1} {W : Type u_2} [inst : Fintype V] (H : SimpleGraph W) (m : ℕ),
  SimpleGraph.extremalNumber (Fintype.card V) H ≤ m ↔
    ∀ ⦃G : SimpleGraph V⦄ [inst_1 : DecidableRel G.Adj], H.Free G → G.edgeFinset.card ≤ m

extremalNumber (card V) H is at most x if and only if every H-free simple graph G has at most x edges.

Defined in

Mathlib.Combinatorics.SimpleGraph.Extremal.Basic

Cited by

4 results in Mathlib

Foundations

Depth 76 from the axioms · uses propext, Classical.choice, Quot.sound

Assumes

Fintype