op_1461_uniquely_k4_saturated_max_degree_n_minus_six
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
- 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…
- 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.
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.
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.
uses
uniquely_k4_saturated_max_degree_six_order_twelveobtain ⟨G, hG⟩ := uniquely_k4_saturated_max_degree_six_order_twelve$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$.
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.
- When $n = 12$, the term $n - 6$ definitionally reduces to $6$, so the hypothesis $hG$ directly matches the target $\Delta(G) = n - 6$ without requiring an explicit arithmetic rewrite.
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.
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⟩