graph_has_no_indep_six
def
A simple graph has no independent set of size 6 if every 6-element subset of vertices contains two distinct adjacent vertices.
Statement
def graph_has_no_indep_six {V : Type*} (G : SimpleGraph V) : Prop
- Defined in
- scout/2610-24484-erd-h-o-s-gy-arf-as-balanced-five-colorings.md:1267
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Used by 2
- card_edgeFinset_ge_55_of_no_indep_sixIf a simple graph on 26 vertices has no independent set of size 6, then it has at least 55 edges.
- balanced_five_coloring_exists_color_class_bounds_and_propertiesFor an arbitrary finite type V with 26 elements, if c : Sym2 V → Fin 5 is a balanced edge coloring, then some color class graph has no…
Read back from the Lean
Given a type V and a simple graph G on V, graph_has_no_indep_six G asserts that for every finite subset S of V, if S has cardinality 6, then there exist elements v ∈ S and w ∈ S such that v and w are adjacent in G.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A graph has no independent set of size 6 if every 6 vertices span at least one edge. -/ def graph_has_no_indep_six {V : Type*} (G : SimpleGraph V) : Prop := ∀ S : Finset V, S.card = 6 → ∃ v ∈ S, ∃ w ∈ S, G.Adj v w