Local linearity: a strongly regular graph with has no
ProvedConway99.srg_lambda_one_cliqueFree_fourA strongly regular graph with is -free.
Let be strongly regular with parameters , so that any two adjacent vertices have exactly one common neighbour. Then contains no clique on four vertices:
Indeed, if were four pairwise adjacent vertices, then and would be two distinct common neighbours of the adjacent pair , contradicting .
For Conway's 99-graph problem this says that a hypothetical graph has clique number exactly : its maximal cliques are the triangles that form the lines of the associated partial linear space. The statement is the local-linearity constraint that a search over such graphs must respect, and it holds for every parameter set with , in particular for the realised cases and .
Formalization note. The vertex type is an arbitrary finite type with decidable equality, and the parameters , , are unconstrained; only is used.
import Mathlib.Combinatorics.SimpleGraph.StronglyRegular import Mathlib.Combinatorics.SimpleGraph.Clique open Finset SimpleGraph
namespace Conway99
theorem srg_lambda_one_cliqueFree_four {V : Type} [Fintype V] [DecidableEq V]
(g : SimpleGraph V) [DecidableRel g.Adj] {n k μ : ℕ} (h : g.IsSRGWith n k 1 μ) :
g.CliqueFree 4 := by sorry
end Conway99