AFTD Auto-Formalizing Theoretical Domains

uniquely_k4_saturated_max_degree_six_order_twelve

theoremverifiedformalization

There exists a simple graph G on Fin 12 such that G is uniquely K_4-saturated and the maximum degree of G equals 6.

Statement

open scoped Classical in
theorem uniquely_k4_saturated_max_degree_six_order_twelve :
    ∃ (G : SimpleGraph (Fin 12)),
      is_uniquely_clique_saturated G 4 ∧ G.maxDegree = 6
Formalizes
arXiv:2611.13656 Sec. 2; Collins and Cooper (cf. Hartke and Stolee 2012)
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • 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…
Used by 2

Read back from the Lean

There exists a simple graph $G$ on the vertex set $\text{Fin } 12$ such that: 1. $G$ is uniquely 4-clique saturated: - $G$ contains no 4-clique (no subset of 4 vertices forms a clique in $G$), and - For every edge $e$ in the edge complement of $G$, adding $e$ to $G$ yields a graph containing exactly one 4-clique; and 2. The maximum vertex degree of $G$ is 6.

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 is proved by explicitly exhibiting the complement of the icosahedral graph on 12 vertices. Because the icosahedral graph is 5-regular, every vertex in its complement has degree 12 - 1 - 5 = 6, yielding a maximum degree of 6. The complement is K_4-free because the icosahedron has independence number 3, and adding any non-edge creates a unique 4-clique corresponding to the antipodal opposite edge in the icosahedron. Lean verifies both the saturation property and the maximum degree by finite exhaustive computation via the `decide` tactic, supported by custom decidability instances that optimize candidate pruning.

  1. Unique existence of a witness for predicate p implies that the filter of the universal finset by p has cardinality 1.

    Using `Finset.card_eq_one`, having cardinality 1 is reformulated as being a singleton {a}. Given unique existence ∃! x, p x with witness x, the filtered finset of all elements satisfying p is shown by extensionality to equal {x}, because p y ↔ y = x by uniqueness.

    lines 6–10

    uses Finset.card_eq_one, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_singleton

      rw [Finset.card_eq_one]
      constructor
      · rintro ⟨x, hx, huniq⟩
        use x; ext y; simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_singleton]
        exact ⟨fun hy => huniq y hy, fun hy => by subst hy; exact hx⟩
  2. If the filter of the universal finset by predicate p has cardinality 1, then there exists a unique witness satisfying p.

    Assuming the filtered finset is a singleton {x}, x belongs to the filter and hence satisfies p x. Furthermore, any y satisfying p y must belong to the filter {x}, which forces y = x. This establishes the equivalence (∃! x, p x) ↔ |{x | p x}| = 1.

    lines 11–17

    uses Finset.mem_singleton_self, Finset.mem_filter, Finset.mem_singleton.mp

      · rintro ⟨x, hx⟩
        have hxmem : x ∈ Finset.filter p Finset.univ := by rw [hx]; exact Finset.mem_singleton_self x
        rw [Finset.mem_filter] at hxmem
        refine ⟨x, hxmem.2, fun y hy => ?_⟩
        have hymem : y ∈ Finset.filter p Finset.univ := by simp [hy]
        rw [hx] at hymem
        exact Finset.mem_singleton.mp hymem
  3. A finset s is an n-clique if and only if its cardinality is n and it induces a clique.

    Rewriting with `SimpleGraph.isNClique_iff` and commuting the conjunction with `and_comm` places the cardinality condition |s| = n before the clique condition. During exhaustive enumeration, this allows candidate subsets of the wrong size to be rejected immediately before evaluating pairwise adjacencies.

    lines 26–30

    uses SimpleGraph.isNClique_iff, and_comm

    lemma uniquely_k4_saturated_max_degree_six_order_twelve_isNClique_iff
        {V : Type*} (G : SimpleGraph V) (n : ℕ) (s : Finset V) :
        G.IsNClique n s ↔ s.card = n ∧ G.IsClique (s : Set V) := by
      rw [SimpleGraph.isNClique_iff, and_comm]
    
  4. The complement adjacency relation icoCompAdjRel is symmetric. automation

    The definition of the complement graph's adjacency relation is unfolded, and symmetry is verified by exhaustive evaluation over all pairs of vertices in Fin 12 using `decide`.

    lines 57–62

    uses uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRel

    lemma uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRel_symm :
        ∀ (u v : Fin 12),
          uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRel u v →
          uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRel v u := by
      intro u v; dsimp [uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRel]; revert u v; decide
    
  5. The complement adjacency relation icoCompAdjRel is irreflexive (loopless). automation

    The definition of icoCompAdjRel is unfolded, and irreflexivity is verified for all 12 vertices by exhaustive evaluation using `decide`.

    lines 63–67

    uses uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRel

    lemma uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRel_irrefl :
        ∀ (u : Fin 12),
          ¬ uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRel u u := by
      intro u; dsimp [uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRel]; revert u; decide
    
  6. The maximum degree of icoCompGraph is 6. automation

    The complement of the icosahedral graph is 6-regular (each vertex has degree 12 - 1 - 5 = 6). The maximum degree across all 12 vertices is evaluated by direct computation using `decide`.

    lines 77–79

    lemma uniquely_k4_saturated_max_degree_six_order_twelve_icoComp_maxDeg :
        uniquely_k4_saturated_max_degree_six_order_twelve_icoCompGraph.maxDegree = 6 := by decide
    
  7. The complement graph icoCompGraph is uniquely K_4-saturated. automation

    Unfolding `is_uniquely_clique_saturated` yields two conditions: icoCompGraph contains no 4-clique, and for every non-edge e, adding e creates a unique 4-clique. Both conditions are verified by finite exhaustive search using `decide`, accelerated by the custom fast decidability instances.

    lines 80–84

    uses is_uniquely_clique_saturated

    lemma uniquely_k4_saturated_max_degree_six_order_twelve_icoComp_sat :
        is_uniquely_clique_saturated uniquely_k4_saturated_max_degree_six_order_twelve_icoCompGraph 4 := by
      dsimp [is_uniquely_clique_saturated]
      decide
    
  8. The maximum degree of icoCompGraph under classical decidability equals 6.

    Using `congr!`, the equality h establishes that evaluating `SimpleGraph.maxDegree` with the noncomputable `Classical.propDecidable` gives the same result as evaluating it with the computable instance `instDecRelAdj`. Rewriting along h and applying the previously verified `icoComp_maxDeg` closes the goal.

    lines 85–94

    uses uniquely_k4_saturated_max_degree_six_order_twelve_icoComp_maxDeg

    lemma uniquely_k4_saturated_max_degree_six_order_twelve_icoComp_maxDeg_classical :
        (@SimpleGraph.maxDegree (Fin 12) uniquely_k4_saturated_max_degree_six_order_twelve_icoCompGraph (Fin.fintype 12)
          fun a b => Classical.propDecidable (uniquely_k4_saturated_max_degree_six_order_twelve_icoCompGraph.Adj a b)) = 6 := by
      have h : (@SimpleGraph.maxDegree (Fin 12) uniquely_k4_saturated_max_degree_six_order_twelve_icoCompGraph (Fin.fintype 12)
          fun a b => Classical.propDecidable (uniquely_k4_saturated_max_degree_six_order_twelve_icoCompGraph.Adj a b)) =
        @SimpleGraph.maxDegree (Fin 12) uniquely_k4_saturated_max_degree_six_order_twelve_icoCompGraph _
          uniquely_k4_saturated_max_degree_six_order_twelve_instDecRelAdj := by congr!
      rw [h]
      exact uniquely_k4_saturated_max_degree_six_order_twelve_icoComp_maxDeg
    
  9. There exists a simple graph on Fin 12 that is uniquely K_4-saturated and has maximum degree 6.

    The complement of the icosahedral graph, `icoCompGraph`, is provided as the explicit witness, combining the saturation certificate `icoComp_sat` and the maximum degree certificate `icoComp_maxDeg_classical`.

    lines 97–102

    uses uniquely_k4_saturated_max_degree_six_order_twelve_icoCompGraph, uniquely_k4_saturated_max_degree_six_order_twelve_icoComp_sat, uniquely_k4_saturated_max_degree_six_order_twelve_icoComp_maxDeg_classical

    theorem uniquely_k4_saturated_max_degree_six_order_twelve :
        ∃ (G : SimpleGraph (Fin 12)),
          is_uniquely_clique_saturated G 4 ∧ G.maxDegree = 6 :=
      ⟨uniquely_k4_saturated_max_degree_six_order_twelve_icoCompGraph,
       uniquely_k4_saturated_max_degree_six_order_twelve_icoComp_sat,
       uniquely_k4_saturated_max_degree_six_order_twelve_icoComp_maxDeg_classical⟩
Finset.card_eq_one
A finite set has cardinality 1 if and only if it is a singleton set {a} for some element a.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
true_and
Conjunction of True with a proposition p simplifies to p.
Finset.mem_singleton
An element belongs to the singleton {a} if and only if it equals a.
Finset.mem_singleton_self
Every element belongs to the singleton set containing itself.
Finset.mem_singleton.mp
If an element belongs to the singleton set {x}, then it equals x.
SimpleGraph.isNClique_iff
A finite set of vertices is an n-clique if and only if it induces a clique and has cardinality n.
and_comm
Logical conjunction is commutative: a ∧ b ↔ b ∧ a.
uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRel
The adjacency relation on Fin 12 defining the complement of the icosahedral graph.
is_uniquely_clique_saturated
A graph is uniquely r-clique saturated if it contains no r-clique, and adding any non-edge creates a unique r-clique.
uniquely_k4_saturated_max_degree_six_order_twelve_icoComp_maxDeg
The maximum degree of the complement of the icosahedral graph equals 6.
uniquely_k4_saturated_max_degree_six_order_twelve_icoCompGraph
The complement of the icosahedral graph, defined as a simple graph on Fin 12.
uniquely_k4_saturated_max_degree_six_order_twelve_icoComp_sat
The complement of the icosahedral graph is uniquely K_4-saturated.
uniquely_k4_saturated_max_degree_six_order_twelve_icoComp_maxDeg_classical
The maximum degree of the complement of the icosahedral graph under classical decidability equals 6.

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

set_option maxRecDepth 50000lemma uniquely_k4_saturated_max_degree_six_order_twelve_existsUnique_iff_card    {α : Type*} [Fintype α] [DecidableEq α] (p : α → Prop) [DecidablePred p] :    (∃! x, p x) ↔ (Finset.filter p Finset.univ).card = 1 := by  rw [Finset.card_eq_one]  constructor  · rintro ⟨x, hx, huniq⟩    use x; ext y; simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_singleton]    exact ⟨fun hy => huniq y hy, fun hy => by subst hy; exact hx⟩  · rintro ⟨x, hx⟩    have hxmem : x ∈ Finset.filter p Finset.univ := by rw [hx]; exact Finset.mem_singleton_self x    rw [Finset.mem_filter] at hxmem    refine ⟨x, hxmem.2, fun y hy => ?_⟩    have hymem : y ∈ Finset.filter p Finset.univ := by simp [hy]    rw [hx] at hymem    exact Finset.mem_singleton.mp hymem@[default_instance 2000]instance uniquely_k4_saturated_max_degree_six_order_twelve_fastDecidableExistsUnique    {α : Type*} [Fintype α] [DecidableEq α] (p : α → Prop) [DecidablePred p] :    Decidable (∃! x, p x) :=  decidable_of_iff ((Finset.filter p Finset.univ).card = 1)    (uniquely_k4_saturated_max_degree_six_order_twelve_existsUnique_iff_card p).symmlemma uniquely_k4_saturated_max_degree_six_order_twelve_isNClique_iff    {V : Type*} (G : SimpleGraph V) (n : ℕ) (s : Finset V) :    G.IsNClique n s ↔ s.card = n ∧ G.IsClique (s : Set V) := by  rw [SimpleGraph.isNClique_iff, and_comm]@[default_instance 2000]instance uniquely_k4_saturated_max_degree_six_order_twelve_fastDecidableIsNClique    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (n : ℕ) (s : Finset V) :    Decidable (G.IsNClique n s) :=  decidable_of_iff (s.card = n ∧ G.IsClique (s : Set V))    (uniquely_k4_saturated_max_degree_six_order_twelve_isNClique_iff G n s).symmdef uniquely_k4_saturated_max_degree_six_order_twelve_icoAdj (u v : Fin 12) : Bool :=  let (a, b) := if u.val ≤ v.val then (u.val, v.val) else (v.val, u.val)  if a == b then false  else if a == 0 then b ≤ 5  else if b == 11 then 6 ≤ a  else if a ≤ 5 && b ≤ 5 then ((a - 1 + 5 - (b - 1)) % 5 == 1) || ((a - 1 + 5 - (b - 1)) % 5 == 4)  else if 6 ≤ a && 6 ≤ b then ((a - 6 + 5 - (b - 6)) % 5 == 1) || ((a - 6 + 5 - (b - 6)) % 5 == 4)  else if a ≤ 5 && 6 ≤ b then    let x := a - 1    let y := b - 6    (y == x) || (y == (x + 1) % 5)  else falsedef uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdj (u v : Fin 12) : Bool :=  u ≠ v && !uniquely_k4_saturated_max_degree_six_order_twelve_icoAdj u vdef uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRel (u v : Fin 12) : Prop :=  uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdj u v = truelemma uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRel_symm :    ∀ (u v : Fin 12),      uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRel u v →      uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRel v u := by  intro u v; dsimp [uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRel]; revert u v; decidelemma uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRel_irrefl :    ∀ (u : Fin 12),      ¬ uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRel u u := by  intro u; dsimp [uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRel]; revert u; decidedef uniquely_k4_saturated_max_degree_six_order_twelve_icoCompGraph : SimpleGraph (Fin 12) where  Adj := uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRel  symm := ⟨uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRel_symm⟩  loopless := ⟨uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRel_irrefl⟩instance uniquely_k4_saturated_max_degree_six_order_twelve_instDecRelAdj :    DecidableRel uniquely_k4_saturated_max_degree_six_order_twelve_icoCompGraph.Adj := fun u v =>  inferInstanceAs (Decidable (uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdj u v = true))lemma uniquely_k4_saturated_max_degree_six_order_twelve_icoComp_maxDeg :    uniquely_k4_saturated_max_degree_six_order_twelve_icoCompGraph.maxDegree = 6 := by decidelemma uniquely_k4_saturated_max_degree_six_order_twelve_icoComp_sat :    is_uniquely_clique_saturated uniquely_k4_saturated_max_degree_six_order_twelve_icoCompGraph 4 := by  dsimp [is_uniquely_clique_saturated]  decidelemma uniquely_k4_saturated_max_degree_six_order_twelve_icoComp_maxDeg_classical :    (@SimpleGraph.maxDegree (Fin 12) uniquely_k4_saturated_max_degree_six_order_twelve_icoCompGraph (Fin.fintype 12)      fun a b => Classical.propDecidable (uniquely_k4_saturated_max_degree_six_order_twelve_icoCompGraph.Adj a b)) = 6 := by  have h : (@SimpleGraph.maxDegree (Fin 12) uniquely_k4_saturated_max_degree_six_order_twelve_icoCompGraph (Fin.fintype 12)      fun a b => Classical.propDecidable (uniquely_k4_saturated_max_degree_six_order_twelve_icoCompGraph.Adj a b)) =    @SimpleGraph.maxDegree (Fin 12) uniquely_k4_saturated_max_degree_six_order_twelve_icoCompGraph _      uniquely_k4_saturated_max_degree_six_order_twelve_instDecRelAdj := by congr!  rw [h]  exact uniquely_k4_saturated_max_degree_six_order_twelve_icoComp_maxDegopen scoped Classical in/-- There exists a uniquely K_4-saturated simple graph on 12 vertices with maximum degree 6 (the complement of the icosahedral graph). -/theorem uniquely_k4_saturated_max_degree_six_order_twelve :    ∃ (G : SimpleGraph (Fin 12)),      is_uniquely_clique_saturated G 4 ∧ G.maxDegree = 6 :=  ⟨uniquely_k4_saturated_max_degree_six_order_twelve_icoCompGraph,   uniquely_k4_saturated_max_degree_six_order_twelve_icoComp_sat,   uniquely_k4_saturated_max_degree_six_order_twelve_icoComp_maxDeg_classical⟩
See it in the graphDiscuss this resultChallenge it