uniquely_k4_saturated_max_degree_six_order_twelve
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
- op_1461_uniquely_k4_saturated_max_degree_n_minus_sixThere 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…
- regular_bipartite_decompose_perfect_matchingsEvery d-regular finite bipartite simple graph decomposes into d spanning one-regular subgraphs: every edge appears in exactly one of them.
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.
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.
uses
Finset.card_eq_one,Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_singletonrw [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⟩
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.
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 hymemA 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.
uses
SimpleGraph.isNClique_iff,and_commlemma 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]
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`.
uses
uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRellemma 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
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`.
uses
uniquely_k4_saturated_max_degree_six_order_twelve_icoCompAdjRellemma 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
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`.
lemma uniquely_k4_saturated_max_degree_six_order_twelve_icoComp_maxDeg : uniquely_k4_saturated_max_degree_six_order_twelve_icoCompGraph.maxDegree = 6 := by decide
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.
uses
is_uniquely_clique_saturatedlemma 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
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.
uses
uniquely_k4_saturated_max_degree_six_order_twelve_icoComp_maxDeglemma 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
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`.
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_classicaltheorem 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.
- The core graph-theoretic properties -- that the complement of the icosahedron contains no 4-cliques, that adding any non-edge creates a unique 4-clique, and that the maximum degree is 6 -- are verified by exhaustive computation via `decide` rather than synthetic geometric arguments.
- The lemmas `existsUnique_iff_card` and `isNClique_iff` and their corresponding typeclass instances are computational optimizations designed to allow `decide` to terminate in feasible time by short-circuiting cardinality checks and reformulating unique existence as a singleton filter.
- The lemma `icoComp_maxDeg_classical` is a formal bookkeeping step reconciling the computable decidability instance used for verification with Lean's noncomputable classical decidability instance used in the theorem statement.
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.
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⟩