Theorems · Theorem · combinatorics

SimpleGraph.IsTuranMaximal.card_parts

∀ {V : Type u_1} [inst : Fintype V] {G : SimpleGraph V} [inst_1 : DecidableRel G.Adj] {r : ℕ} (h : G.IsTuranMaximal r)
  [inst_2 : DecidableEq V], h.finpartition.parts.card = min (Fintype.card V) r

There are min n r parts in a graph on n vertices satisfying G.IsTuranMaximal r. min handles the n < r case, when G is complete but still r + 1-cliquefree for having insufficiently many vertices.

Defined in

Mathlib.Combinatorics.SimpleGraph.Extremal.Turan

Cited by

1 results in Mathlib

Foundations

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

Assumes

FintypeDecidableRelDecidableEq