is_uniquely_clique_saturated
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
- uniquely_clique_saturated_vertex_deleted_of_universalLet r ≥ 3 be an integer, and let G be a finite simple graph. If G is uniquely K_r-saturated and x is a universal vertex of G, then the…
- uniquely_clique_saturated_coneLet r ≥ 3 be an integer, and let G be a finite simple graph. If G is uniquely K_r-saturated, then the cone G ∨ K_1 is uniquely…
- uniquely_k4_saturated_max_degree_ge_threeFor every finite simple graph G on at least 4 vertices, if G is uniquely K_4-saturated, then the maximum degree of G is at least 3.
- not_uniquely_k4_saturated_no_max_degree_n_minus_two_or_fourThe statement
uniquely_k4_saturated_no_max_degree_n_minus_two_or_fouris false: The theorem quantifies over ALL n : ℕ, including n = 0… - op_1461_uniquely_k4_saturated_max_degree_n_minus_sixThere exists a natural number n ≥ 7 and a simple graph G on Fin n such that G is uniquely K_4-saturated and the maximum degree of G equals…
- uniquely_k4_saturated_max_degree_six_order_twelveThere exists a simple graph G on Fin 12 such that G is uniquely K_4-saturated and the maximum degree of G equals 6.
- uniquely_k4_saturated_no_max_degree_n_minus_six_of_le_eightFor every natural number n with 4 ≤ n ≤ 8 and every simple graph G on Fin n, if G is uniquely K_4-saturated, then the maximum degree of G…
- uniquely_clique_saturated_universal_and_coneLet r ≥ 3 be an integer, and let G be a finite simple graph. If G is uniquely K_r-saturated, then (i) for every universal vertex x of G,…
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)