AFTD Auto-Formalizing Theoretical Domains

uniquely_clique_saturated_universal_and_cone

theoremverifiedformalization

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.

  1. 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`.

    lines 7–8

    uses uniquely_clique_saturated_vertex_deleted_of_universal, uniquely_clique_saturated_cone

      exact ⟨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

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