AFTD Auto-Formalizing Theoretical Domains

uniquely_k4_saturated_max_degree_ge_three

theoremverified

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

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.

  1. 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.

    lines 8–10

    uses Finset.exists_subset_card_eq

      classical
      obtain ⟨s0, -, hs0card⟩ :=
        Finset.exists_subset_card_eq (s := (Finset.univ : Finset V)) (by simpa using hn)
  2. 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.

    lines 11–17

      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⟩
  3. 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.

    lines 18–22

    uses SimpleGraph.mem_edgeSet, SimpleGraph.compl_adj

      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
  4. 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`.

    lines 23–32

    uses Finset.card_le_card, Finset.card_pair, Finset.not_subset.mp, Finset.mem_insert, Finset.mem_singleton, not_or

      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
  5. 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`.

    lines 33–48

    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_iff

      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
  6. 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`).

    lines 49–52

    uses Finset.card_erase_of_mem

      have hcard3 : (t.erase c).card = 3 := by
        have := Finset.card_erase_of_mem hct
        have ht4 := ht.card_eq
        omega
  7. 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`.

    lines 53–56

    uses Finset.card_le_card, SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.degree_le_maxDegree

      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
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.

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/-- 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
See it in the graphDiscuss this resultChallenge it