AFTD Auto-Formalizing Theoretical Domains

simple_graph_pair_stable_support_max_k4_anchor_internal

theoremverified

In a two-edge-stable graph, every fourth vertex completing a packed triangle of a support-maximal maximum triangle packing to a four-clique already belongs to the packing vertex support.

Statement

theorem simple_graph_pair_stable_support_max_k4_anchor_internal (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (P : Finset (Finset (Fin n))) (htri : ∀ t ∈ P, G.IsNClique 3 t) (hdisj : (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1)) (hsupport : ∀ Q : Finset (Finset (Fin n)), (∀ t ∈ Q, G.IsNClique 3 t) → (Q : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1) → Q.card = P.card → (Q.biUnion id).card ≤ (P.biUnion id).card) (hmax : P.card = simple_graph_triangle_packing_number G) (hstable : ∀ e f : Sym2 (Fin n), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f → simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G) (a b c x : Fin n) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n))) : x ∈ P.biUnion id
Source
Internal-anchor reduction for the general fully forced triangle-packing residual; no novelty claim.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

The proof, explained

The proof argues by contradiction. If the fourth vertex x extending a packed triangle {a, b, c} to a 4-clique lay outside the vertex support of the support-maximal maximum packing P, deleting the two distinct edges s(a, b) and s(c, x) would strictly decrease the triangle packing number by simple_graph_support_max_packing_external_k4_decreases_packing. However, the graph is two-edge-stable, so deleting any two distinct edges preserves the packing number. This contradiction forces x to already belong to the vertex support of P.

  1. The four vertices a, b, c, and x forming the 4-clique are pairwise distinct.

    Because {a, b, c, x} is a 4-clique, its cardinality is 4. If any two vertices were equal, the set {a, b, c, x} would be contained in a 3-element set, which by Finset.card_le_card and Finset.card_le_three would imply that its cardinality is at most 3. This contradiction shows that a ≠ b, a ≠ c, a ≠ x, b ≠ c, b ≠ x, and c ≠ x.

    lines 6–72

    uses Finset.card_le_card, Finset.card_le_three, Finset.mem_insert, Finset.mem_singleton

      classical
      have hab : a ≠ b := by
        intro h
        have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,c,x} := by
          intro v hv
          simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢
          clear * - h hv
          aesop
        have hc := Finset.card_le_card hs
        have hb := Finset.card_le_three (a := a) (b := c) (c := x)
        have h4 := hk4.card_eq
        omega
      have hac : a ≠ c := by
        intro h
        have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,b,x} := by
          intro v hv
          simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢
          clear * - h hv
          aesop
        have hc := Finset.card_le_card hs
        have hb := Finset.card_le_three (a := a) (b := b) (c := x)
        have h4 := hk4.card_eq
        omega
      have hax : a ≠ x := by
        intro h
        have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,b,c} := by
          intro v hv
          simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢
          clear * - h hv
          aesop
        have hc := Finset.card_le_card hs
        have hb := Finset.card_le_three (a := a) (b := b) (c := c)
        have h4 := hk4.card_eq
        omega
      have hbc : b ≠ c := by
        intro h
        have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,b,x} := by
          intro v hv
          simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢
          clear * - h hv
          aesop
        have hc := Finset.card_le_card hs
        have hb := Finset.card_le_three (a := a) (b := b) (c := x)
        have h4 := hk4.card_eq
        omega
      have hbx : b ≠ x := by
        intro h
        have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,b,c} := by
          intro v hv
          simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢
          clear * - h hv
          aesop
        have hc := Finset.card_le_card hs
        have hb := Finset.card_le_three (a := a) (b := b) (c := c)
        have h4 := hk4.card_eq
        omega
      have hcx : c ≠ x := by
        intro h
        have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,b,c} := by
          intro v hv
          simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢
          clear * - h hv
          aesop
        have hc := Finset.card_le_card hs
        have hb := Finset.card_le_three (a := a) (b := b) (c := c)
        have h4 := hk4.card_eq
        omega
  2. Assuming for contradiction that x lies outside the packing support, s(a, b) and s(c, x) are two distinct edges of G.

    Suppose for contradiction that x ∉ ⋃ P. Because {a, b, c, x} is a 4-clique, any two distinct vertices in it are joined by an edge in G. Since a ≠ b and c ≠ x, both s(a, b) and s(c, x) are edges of G. Furthermore, because all four vertices are distinct, Sym2.eq_iff verifies that the two edges are distinct: s(a, b) ≠ s(c, x).

    lines 73–82

    uses Sym2.eq_iff

      by_contra hx
      have he : s(a,b) ∈ G.edgeSet := by
        have ha : a ∈ ({a,b,c,x} : Finset (Fin n)) := by simp
        have hb : b ∈ ({a,b,c,x} : Finset (Fin n)) := by simp
        exact hk4.isClique ha hb hab
      have hf : s(c,x) ∈ G.edgeSet := by
        have hc : c ∈ ({a,b,c,x} : Finset (Fin n)) := by simp
        have hx' : x ∈ ({a,b,c,x} : Finset (Fin n)) := by simp
        exact hk4.isClique hc hx' hcx
      have hef : s(a,b) ≠ s(c,x) := by simp [Sym2.eq_iff,hac,hax,hbc,hbx]
  3. Deleting the two edges contradicts the two-edge stability of G, proving x must belong to the packing support.

    By simple_graph_support_max_packing_external_k4_decreases_packing, deleting the two edges s(a, b) and s(c, x) strictly decreases the triangle packing number of G. On the other hand, the two-edge stability hypothesis (hstable) asserts that deleting any two distinct edges leaves the triangle packing number unchanged. Linear arithmetic (omega) derives False from this contradiction, concluding that x ∈ ⋃ P.

    lines 83–85

    uses simple_graph_support_max_packing_external_k4_decreases_packing

      have hd := simple_graph_support_max_packing_external_k4_decreases_packing n G P htri hdisj hsupport hmax a b c x hp hx hk4
      have hs := hstable s(a,b) s(c,x) he hf hef
      omega
Finset.card_le_card
If a finite set s is a subset of t, then the cardinality of s is at most the cardinality of t.
Finset.card_le_three
Any set formed by inserting three elements into the empty set has cardinality at most 3.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to the singleton set {a} if and only if it equals a.
Sym2.eq_iff
Two unordered pairs s(x, y) and s(z, w) are equal if and only if {x, y} = {z, w}.
simple_graph_support_max_packing_external_k4_decreases_packing
If P is a maximum triangle packing with maximal vertex support and a packed triangle {a, b, c} extends to a 4-clique with an external vertex x, deleting {a, b} and {c, x} strictly decreases the triangle packing number.

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 Sym2set_option maxRecDepth 10000set_option maxHeartbeats 3000000theorem simple_graph_pair_stable_support_max_k4_anchor_internal (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (P : Finset (Finset (Fin n))) (htri : ∀ t ∈ P, G.IsNClique 3 t) (hdisj : (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1)) (hsupport : ∀ Q : Finset (Finset (Fin n)), (∀ t ∈ Q, G.IsNClique 3 t) → (Q : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1) → Q.card = P.card → (Q.biUnion id).card ≤ (P.biUnion id).card) (hmax : P.card = simple_graph_triangle_packing_number G) (hstable : ∀ e f : Sym2 (Fin n), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f → simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G) (a b c x : Fin n) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n))) : x ∈ P.biUnion id := by  classical  have hab : a ≠ b := by    intro h    have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,c,x} := by      intro v hv      simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢      clear * - h hv      aesop    have hc := Finset.card_le_card hs    have hb := Finset.card_le_three (a := a) (b := c) (c := x)    have h4 := hk4.card_eq    omega  have hac : a ≠ c := by    intro h    have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,b,x} := by      intro v hv      simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢      clear * - h hv      aesop    have hc := Finset.card_le_card hs    have hb := Finset.card_le_three (a := a) (b := b) (c := x)    have h4 := hk4.card_eq    omega  have hax : a ≠ x := by    intro h    have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,b,c} := by      intro v hv      simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢      clear * - h hv      aesop    have hc := Finset.card_le_card hs    have hb := Finset.card_le_three (a := a) (b := b) (c := c)    have h4 := hk4.card_eq    omega  have hbc : b ≠ c := by    intro h    have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,b,x} := by      intro v hv      simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢      clear * - h hv      aesop    have hc := Finset.card_le_card hs    have hb := Finset.card_le_three (a := a) (b := b) (c := x)    have h4 := hk4.card_eq    omega  have hbx : b ≠ x := by    intro h    have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,b,c} := by      intro v hv      simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢      clear * - h hv      aesop    have hc := Finset.card_le_card hs    have hb := Finset.card_le_three (a := a) (b := b) (c := c)    have h4 := hk4.card_eq    omega  have hcx : c ≠ x := by    intro h    have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,b,c} := by      intro v hv      simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢      clear * - h hv      aesop    have hc := Finset.card_le_card hs    have hb := Finset.card_le_three (a := a) (b := b) (c := c)    have h4 := hk4.card_eq    omega  by_contra hx  have he : s(a,b) ∈ G.edgeSet := by    have ha : a ∈ ({a,b,c,x} : Finset (Fin n)) := by simp    have hb : b ∈ ({a,b,c,x} : Finset (Fin n)) := by simp    exact hk4.isClique ha hb hab  have hf : s(c,x) ∈ G.edgeSet := by    have hc : c ∈ ({a,b,c,x} : Finset (Fin n)) := by simp    have hx' : x ∈ ({a,b,c,x} : Finset (Fin n)) := by simp    exact hk4.isClique hc hx' hcx  have hef : s(a,b) ≠ s(c,x) := by simp [Sym2.eq_iff,hac,hax,hbc,hbx]  have hd := simple_graph_support_max_packing_external_k4_decreases_packing n G P htri hdisj hsupport hmax a b c x hp hx hk4  have hs := hstable s(a,b) s(c,x) he hf hef  omega
See it in the graphDiscuss this resultChallenge it