AFTD Auto-Formalizing Theoretical Domains

is_uniquely_clique_saturated

def

A simple graph G is uniquely K_r-saturated if it contains no clique of size r, but adding any non-edge e to G creates exactly one clique of size r.

Statement

def is_uniquely_clique_saturated {V : Type*} (G : SimpleGraph V) (r : ℕ) : Prop
Defined in
arXiv:2611.13656 Section 1
Verified
12 Nov 2026
Axioms
none listed
Used by 8

Read back from the Lean

Given a type V, a simple graph G on V, and a natural number r, is_uniquely_clique_saturated G r asserts that both of the following hold: 1. G contains no clique of cardinality r: for every finite subset s : Finset V, s is not an r-clique of G (i.e., ¬ G.IsNClique r s). 2. Adding any missing edge to G creates exactly one r-clique: for every edge e in the complement graph Gᶜ (that is, every pair of distinct non-adjacent vertices in G), there exists a unique finite subset s : Finset V such that s is an r-clique in the graph G ⊔ SimpleGraph.fromEdgeSet {e} (the graph obtained by adding e to 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 simple graph is uniquely K_r-saturated if it has no r-clique, but adding any non-edge produces a unique r-clique. -/
def is_uniquely_clique_saturated {V : Type*} (G : SimpleGraph V) (r : ℕ) : Prop :=
  (∀ s : Finset V, ¬ G.IsNClique r s) ∧
  (∀ e ∈ Gᶜ.edgeSet, ∃! s : Finset V, (G ⊔ SimpleGraph.fromEdgeSet {e}).IsNClique r s)
See it in the graphDiscuss this resultChallenge it