AFTD Auto-Formalizing Theoretical Domains

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

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
See it in the graphDiscuss this resultChallenge it