uniquely_k4_saturated_max_degree_ge_three
For every finite simple graph G on at least 4 vertices, if G is uniquely K_4-saturated, then the maximum degree of G is at least 3.
Statement
open scoped Classical in theorem uniquely_k4_saturated_max_degree_ge_three {V : Type*} [Fintype V] (G : SimpleGraph V) (hn : 4 ≤ Fintype.card V) (hG : is_uniquely_clique_saturated G 4) : 3 ≤ G.maxDegree
- Source
- arXiv:2611.13656 Sec. 1
- 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 1
- uniquely_k4_saturated_no_max_degree_n_minus_six_of_le_eightFor every natural number n with 4 ≤ n ≤ 8 and every simple graph G on Fin n, if G is uniquely K_4-saturated, then the maximum degree of G…
Read back from the Lean
For every finite type V with at least 4 elements, and every simple graph G on V: if G is uniquely 4-clique-saturated (meaning G contains no 4-clique, and for every edge e in the complement graph Gᶜ, adding e to G creates exactly one 4-clique), then the maximum degree of G is at least 3.
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
Since G has at least 4 vertices and contains no K₄, it cannot be a complete graph, so there exists a non-edge {u, v}. By the saturation hypothesis, adding {u, v} to G creates a 4-clique t. Because t contains 4 vertices, there is some vertex c ∈ t distinct from both u and v. Since c is not an endpoint of the newly added edge {u, v}, all three other vertices in t must be neighbors of c in the original graph G, which shows that c has degree at least 3 and therefore the maximum degree of G is at least 3.
There exists a 4-element subset of vertices s₀ ⊆ V.
By the hypothesis that the vertex set V has at least 4 elements, `Finset.exists_subset_card_eq` yields a 4-element subset s₀ of V.
uses
Finset.exists_subset_card_eqclassical obtain ⟨s0, -, hs0card⟩ := Finset.exists_subset_card_eq (s := (Finset.univ : Finset V)) (by simpa using hn)
There exists a pair of distinct, non-adjacent vertices u and v in G.
Suppose for contradiction that all pairs of distinct vertices in V are adjacent. Then the 4-element set s₀ would form a 4-clique in G, contradicting the first condition of unique K₄-saturation (hG.1), which states that G contains no 4-clique.
have hex : ∃ u v : V, u ≠ v ∧ ¬ G.Adj u v := by by_contra h have hclique : G.IsClique ↑s0 := by intro a ha b hb hab by_contra hnab exact h ⟨a, b, hab, hnab⟩ exact hG.1 s0 ⟨hclique, hs0card⟩
Adding the non-edge {u, v} to G creates a 4-clique t.
Let u and v be distinct non-adjacent vertices. The pair s(u, v) is an edge of the complement graph Gᶜ by `SimpleGraph.mem_edgeSet` and `SimpleGraph.compl_adj`. By the saturation condition of G (hG.2), adding this edge to G yields a 4-clique t.
uses
SimpleGraph.mem_edgeSet,SimpleGraph.compl_adjobtain ⟨u, v, huv, hnv⟩ := hex have he : s(u, v) ∈ Gᶜ.edgeSet := by rw [SimpleGraph.mem_edgeSet] exact (SimpleGraph.compl_adj G u v).mpr ⟨huv, hnv⟩ obtain ⟨t, ht, -⟩ := hG.2 s(u, v) he
The clique t contains a vertex c distinct from both u and v.
The 4-clique t cannot be a subset of {u, v}: if it were, we would have 4 = |t| ≤ |{u, v}| = 2 by `Finset.card_le_card` and `Finset.card_pair`, which is impossible by linear arithmetic (`omega`). Thus, by `Finset.not_subset.mp`, there exists c ∈ t with c ∉ {u, v}, so c ≠ u and c ≠ v by `Finset.mem_insert`, `Finset.mem_singleton`, and `not_or`.
uses
Finset.card_le_card,Finset.card_pair,Finset.not_subset.mp,Finset.mem_insert,Finset.mem_singleton,not_orhave hnotsub : ¬ t ⊆ ({u, v} : Finset V) := by intro hsub have hcard := Finset.card_le_card hsub have h2 : ({u, v} : Finset V).card ≤ 2 := by rw [Finset.card_pair huv] have ht4 := ht.card_eq omega obtain ⟨c, hct, hcuv⟩ := Finset.not_subset.mp hnotsub simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hcuv obtain ⟨hcu, hcv⟩ := hcuv
Every vertex in t \ {c} is adjacent to c in G.
For any x ∈ t \ {c} (unfolded with `Finset.mem_erase`), x and c are distinct vertices in the clique t, so they are adjacent in G ⊔ {s(u, v)} by `Finset.mem_coe.mpr` and `Ne.symm`. By `SimpleGraph.sup_adj`, this adjacency comes either from G or from the added edge s(u, v). If it were the added edge, rewriting with `SimpleGraph.fromEdgeSet_adj`, `Set.mem_singleton_iff`, and `Sym2.eq_iff` implies that {c, x} = {u, v}, forcing c = u or c = v, which contradicts our choice of c. Therefore, c is adjacent to x in G, placing x in the neighbor finset of c by `SimpleGraph.mem_neighborFinset`.
uses
Finset.mem_erase,SimpleGraph.mem_neighborFinset,Finset.mem_coe.mpr,Ne.symm,SimpleGraph.sup_adj,SimpleGraph.fromEdgeSet_adj,Set.mem_singleton_iff,Sym2.eq_iffhave hsub : t.erase c ⊆ G.neighborFinset c := by intro x hx rw [Finset.mem_erase] at hx obtain ⟨hxc, hxt⟩ := hx rw [SimpleGraph.mem_neighborFinset] have hadj : (G ⊔ SimpleGraph.fromEdgeSet {s(u, v)}).Adj c x := ht.isClique (Finset.mem_coe.mpr hct) (Finset.mem_coe.mpr hxt) (Ne.symm hxc) rw [SimpleGraph.sup_adj] at hadj rcases hadj with hGadj | hnew · exact hGadj · simp only [SimpleGraph.fromEdgeSet_adj, Set.mem_singleton_iff] at hnew obtain ⟨heq, -⟩ := hnew rw [Sym2.eq_iff] at heq rcases heq with ⟨rfl, -⟩ | ⟨rfl, -⟩ · exact absurd rfl hcu · exact absurd rfl hcv
The set t \ {c} has cardinality 3.
Since c ∈ t and |t| = 4, removing c leaves a set of cardinality 4 - 1 = 3 by `Finset.card_erase_of_mem` and arithmetic (`omega`).
uses
Finset.card_erase_of_memhave hcard3 : (t.erase c).card = 3 := by have := Finset.card_erase_of_mem hct have ht4 := ht.card_eq omega
The maximum degree of G is at least 3.
Since t \ {c} is a subset of c's neighborhood in G, we have 3 = |t \ {c}| ≤ |N_G(c)| by `Finset.card_le_card`. The size of N_G(c) equals the degree of c by `SimpleGraph.card_neighborFinset_eq_degree`, which is bounded above by G.maxDegree by `SimpleGraph.degree_le_maxDegree`.
uses
Finset.card_le_card,SimpleGraph.card_neighborFinset_eq_degree,SimpleGraph.degree_le_maxDegreecalc 3 = (t.erase c).card := hcard3.symm _ ≤ (G.neighborFinset c).card := Finset.card_le_card hsub _ = G.degree c := SimpleGraph.card_neighborFinset_eq_degree G c _ ≤ G.maxDegree := SimpleGraph.degree_le_maxDegree G c
Finset.exists_subset_card_eq- A finite set with at least n elements contains a subset with exactly n elements.
SimpleGraph.mem_edgeSet- An unordered pair of vertices belongs to the edge set of a graph if and only if those vertices are adjacent.
SimpleGraph.compl_adj- Two vertices are adjacent in the complement graph if and only if they are distinct and not adjacent in the original graph.
Finset.card_le_card- If s is a subset of t, then the cardinality of s is at most the cardinality of t.
Finset.card_pair- A set consisting of two distinct elements has cardinality 2.
Finset.not_subset.mp- If s is not a subset of t, then there exists an element in s that is not in t.
Finset.mem_insert- An element belongs to insert a s if and only if it equals a or belongs to s.
Finset.mem_singleton- An element belongs to {a} if and only if it equals a.
not_or- The negation of p ∨ q is equivalent to ¬p ∧ ¬q.
Finset.mem_erase- An element belongs to s.erase a if and only if it is not equal to a and belongs to s.
SimpleGraph.mem_neighborFinset- A vertex w belongs to the neighbor set of v if and only if v and w are adjacent.
Finset.mem_coe.mpr- Membership of an element in a finset is equivalent to membership in its coerced set.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
SimpleGraph.sup_adj- Two vertices are adjacent in the union of two graphs if and only if they are adjacent in at least one of them.
SimpleGraph.fromEdgeSet_adj- Two vertices are adjacent in the graph generated by an edge set if and only if they are distinct and the edge connecting them belongs to that set.
Set.mem_singleton_iff- An element belongs to the singleton set {b} if and only if it equals b.
Sym2.eq_iff- Two unordered pairs s(x, y) and s(z, w) are equal if and only if (x = z ∧ y = w) or (x = w ∧ y = z).
Finset.card_erase_of_mem- Removing an element from a finite set that contains it decreases the cardinality by 1.
SimpleGraph.card_neighborFinset_eq_degree- The cardinality of the neighbor finset of a vertex equals its degree.
SimpleGraph.degree_le_maxDegree- The degree of any vertex in a finite graph is at most the maximum degree of the graph.
- The automated linear arithmetic tactic `omega` is used on lines 29 and 52 to close simple arithmetic goals ($4 \le 2 \implies \text{False}$ and $4 - 1 = 3$).
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/-- Every uniquely K_4-saturated simple graph on at least 4 vertices has maximum degree at least 3. -/theorem uniquely_k4_saturated_max_degree_ge_three {V : Type*} [Fintype V] (G : SimpleGraph V) (hn : 4 ≤ Fintype.card V) (hG : is_uniquely_clique_saturated G 4) : 3 ≤ G.maxDegree := by classical obtain ⟨s0, -, hs0card⟩ := Finset.exists_subset_card_eq (s := (Finset.univ : Finset V)) (by simpa using hn) have hex : ∃ u v : V, u ≠ v ∧ ¬ G.Adj u v := by by_contra h have hclique : G.IsClique ↑s0 := by intro a ha b hb hab by_contra hnab exact h ⟨a, b, hab, hnab⟩ exact hG.1 s0 ⟨hclique, hs0card⟩ obtain ⟨u, v, huv, hnv⟩ := hex have he : s(u, v) ∈ Gᶜ.edgeSet := by rw [SimpleGraph.mem_edgeSet] exact (SimpleGraph.compl_adj G u v).mpr ⟨huv, hnv⟩ obtain ⟨t, ht, -⟩ := hG.2 s(u, v) he have hnotsub : ¬ t ⊆ ({u, v} : Finset V) := by intro hsub have hcard := Finset.card_le_card hsub have h2 : ({u, v} : Finset V).card ≤ 2 := by rw [Finset.card_pair huv] have ht4 := ht.card_eq omega obtain ⟨c, hct, hcuv⟩ := Finset.not_subset.mp hnotsub simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hcuv obtain ⟨hcu, hcv⟩ := hcuv have hsub : t.erase c ⊆ G.neighborFinset c := by intro x hx rw [Finset.mem_erase] at hx obtain ⟨hxc, hxt⟩ := hx rw [SimpleGraph.mem_neighborFinset] have hadj : (G ⊔ SimpleGraph.fromEdgeSet {s(u, v)}).Adj c x := ht.isClique (Finset.mem_coe.mpr hct) (Finset.mem_coe.mpr hxt) (Ne.symm hxc) rw [SimpleGraph.sup_adj] at hadj rcases hadj with hGadj | hnew · exact hGadj · simp only [SimpleGraph.fromEdgeSet_adj, Set.mem_singleton_iff] at hnew obtain ⟨heq, -⟩ := hnew rw [Sym2.eq_iff] at heq rcases heq with ⟨rfl, -⟩ | ⟨rfl, -⟩ · exact absurd rfl hcu · exact absurd rfl hcv have hcard3 : (t.erase c).card = 3 := by have := Finset.card_erase_of_mem hct have ht4 := ht.card_eq omega calc 3 = (t.erase c).card := hcard3.symm _ ≤ (G.neighborFinset c).card := Finset.card_le_card hsub _ = G.degree c := SimpleGraph.card_neighborFinset_eq_degree G c _ ≤ G.maxDegree := SimpleGraph.degree_le_maxDegree G c