AFTD Auto-Formalizing Theoretical Domains

op_1461_uniquely_k4_saturated_max_degree_n_minus_six

theoremverifiedformalization

There 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 n - 6.

Statement

open scoped Classical in
theorem op_1461_uniquely_k4_saturated_max_degree_n_minus_six :
    ∃ (n : ℕ), 7 ≤ n ∧ ∃ (G : SimpleGraph (Fin n)),
      is_uniquely_clique_saturated G 4 ∧ G.maxDegree = n - 6
Formalizes
arXiv:2611.13656 Sec. 3
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

Read back from the Lean

There exists a natural number $n \ge 7$ and a simple graph $G$ on the vertex set Fin n such that: 1. $G$ is uniquely 4-clique-saturated: $G$ contains no 4-clique, and for every edge $e$ in the complement graph of $G$ (i.e., every pair of distinct non-adjacent vertices), adding $e$ to $G$ yields a graph containing a unique 4-clique; and 2. The maximum degree of $G$ is $n - 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 asserts the existence of an integer $n \ge 7$ and a uniquely $K_4$-saturated graph on $n$ vertices with maximum degree $n - 6$. The proof provides an explicit witness by setting $n = 12$, using a previously established theorem that constructs a uniquely $K_4$-saturated graph on 12 vertices with maximum degree 6. Since $7 \le 12$ and $12 - 6 = 6$, this graph directly satisfies all required properties.

  1. There exists a simple graph $G$ on 12 vertices that is uniquely $K_4$-saturated with maximum degree 6

    We invoke the known theorem `uniquely_k4_saturated_max_degree_six_order_twelve` to obtain such a graph $G$ on `Fin 12` along with the certificate $hG$ that $G$ is uniquely $K_4$-saturated and has maximum degree 6.

    line 6

    uses uniquely_k4_saturated_max_degree_six_order_twelve

      obtain ⟨G, hG⟩ := uniquely_k4_saturated_max_degree_six_order_twelve
  2. $n = 12$ and the graph $G$ witness the existential statement

    We supply $n = 12$ as the witness. The inequality $7 \le 12$ is verified by computational decision (`decide`), and the graph $G$ together with $hG$ satisfies the remaining conditions since $12 - 6 = 6$.

    line 7

      exact ⟨12, by decide, G, hG⟩
uniquely_k4_saturated_max_degree_six_order_twelve
There exists a simple graph on 12 vertices that is uniquely $K_4$-saturated and has maximum degree 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

open scoped Classical in/-- Existence of a uniquely K_4-saturated graph on n vertices with maximum degree n - 6 for some n ≥ 7 (OP-1461). -/theorem op_1461_uniquely_k4_saturated_max_degree_n_minus_six :    ∃ (n : ℕ), 7 ≤ n ∧ ∃ (G : SimpleGraph (Fin n)),      is_uniquely_clique_saturated G 4 ∧ G.maxDegree = n - 6 := by  obtain ⟨G, hG⟩ := uniquely_k4_saturated_max_degree_six_order_twelve  exact ⟨12, by decide, G, hG⟩
See it in the graphDiscuss this resultChallenge it