uniquely_clique_saturated_universal_and_cone
Let 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, the vertex-deleted subgraph G - x is uniquely K_{r-1}-saturated, and (ii) the cone G ∨ K_1 is uniquely K_{r+1}-saturated.
Statement
theorem uniquely_clique_saturated_universal_and_cone {V : Type*} [Fintype V] (G : SimpleGraph V) {r : ℕ} (hr : 3 ≤ r) (hG : is_uniquely_clique_saturated G r) : (∀ x : V, G.IsUniversal x → is_uniquely_clique_saturated (G.induce (Set.univ \ {x})) (r - 1)) ∧ is_uniquely_clique_saturated (simple_graph_cone G) (r + 1)
- Formalizes
- arXiv:2611.13656 Proposition 2.1
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- is_uniquely_clique_saturatedA 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…
- simple_graph_coneThe cone or graph join G ∨ K_1 of a simple graph G is the simple graph on Option V obtained by adding a universal vertex none adjacent to…
- 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…
Read back from the Lean
Let $V$ be a finite type, and let $G$ be a simple graph on $V$. Let $r \ge 3$ be a natural number. Assume that $G$ is uniquely $r$-clique saturated (that is, $G$ contains no clique of size $r$, and for every non-edge $e$ of $G$, adding $e$ to $G$ produces exactly one clique of size $r$).
Then both of the following hold:
1. For every vertex $x \in V$, if $x$ is universal in $G$ (G.IsUniversal x), then the subgraph of $G$ induced on $V \setminus \{x\}$ (specifically, on the subtype {y : V // y ∈ Set.univ \ {x}}) is uniquely $(r - 1)$-clique saturated.
2. The cone graph over $G$ (simple_graph_cone G, formed by adding an apex vertex none adjacent to all vertices of $G$) is uniquely $(r + 1)$-clique saturated.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem packages two complementary operations on uniquely clique-saturated graphs into a single statement. The proof combines the two parts by constructing the pair directly from previously proved lemmas: `uniquely_clique_saturated_vertex_deleted_of_universal` for the universal vertex deletion, and `uniquely_clique_saturated_cone` for the cone construction.
Deleting any universal vertex from G yields a uniquely K_{r-1}-saturated graph, and the cone G ∨ K_1 is uniquely K_{r+1}-saturated.
The theorem asserts a conjunction of two properties. The first clause is verified by taking an arbitrary vertex x with hypothesis hx that x is universal in G, and invoking `uniquely_clique_saturated_vertex_deleted_of_universal`. The second clause is closed directly by invoking `uniquely_clique_saturated_cone`.
uses
uniquely_clique_saturated_vertex_deleted_of_universal,uniquely_clique_saturated_coneexact ⟨fun x hx => uniquely_clique_saturated_vertex_deleted_of_universal G hr hG x hx, uniquely_clique_saturated_cone G hr hG⟩
uniquely_clique_saturated_vertex_deleted_of_universal- If G is uniquely K_r-saturated with r ≥ 3, deleting a universal vertex x yields a uniquely K_{r-1}-saturated graph on V \ {x}.
uniquely_clique_saturated_cone- If G is uniquely K_r-saturated with r ≥ 3, the cone extension G ∨ K_1 is uniquely K_{r+1}-saturated.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Universal vertices and cone extensions in uniquely clique-saturated graphs (Proposition 2.1). -/theorem uniquely_clique_saturated_universal_and_cone {V : Type*} [Fintype V] (G : SimpleGraph V) {r : ℕ} (hr : 3 ≤ r) (hG : is_uniquely_clique_saturated G r) : (∀ x : V, G.IsUniversal x → is_uniquely_clique_saturated (G.induce (Set.univ \ {x})) (r - 1)) ∧ is_uniquely_clique_saturated (simple_graph_cone G) (r + 1) := by exact ⟨fun x hx => uniquely_clique_saturated_vertex_deleted_of_universal G hr hG x hx, uniquely_clique_saturated_cone G hr hG⟩