AFTD Auto-Formalizing Theoretical Domains

simple_graph_support_max_packing_outside_swap_private

theoremverified

If P has maximum vertex support among triangle packings of its size, replacing packed triangle abc by abx with x outside P is possible only if c belongs to no other triangle of P.

Statement

theorem simple_graph_support_max_packing_outside_swap_private (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) (a b c x : Fin n) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hx : x ∉ P.biUnion id) (hface : G.IsNClique 3 ({a,b,x} : Finset (Fin n))) : ∀ q ∈ P, q ≠ ({a,b,c} : Finset (Fin n)) → c ∉ q
Source
Support-maximal exchange reduction for the general pair-stable triangle-packing residual; no novelty claim.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

The theorem is proved by contradiction: suppose some other triangle q ∈ P \ {p} contains c. We consider the swapped packing Q = (P \ {p}) ∪ {t}, where p = {a, b, c} is replaced by t = {a, b, x}. Since x lies outside the vertex support of P, t shares at most one vertex with every other triangle in P, making Q a valid pairwise edge-disjoint triangle packing with |Q| = |P|. However, Q covers all vertices of P (since a, b ∈ t and c ∈ q) plus the new vertex x, strictly increasing the vertex support and contradicting the maximality of P.

  1. The vertex x does not belong to any triangle in P, so in particular x ∉ p.

    Define p = {a, b, c} and t = {a, b, x}. By hypothesis, x is not in the vertex support of P (the union of all triangles in P). Thus x cannot belong to any member q ∈ P, and since p ∈ P, x ∉ p.

    lines 6–14

    uses Finset.mem_biUnion.mpr

      classical
      let p : Finset (Fin n) := {a,b,c}
      let t : Finset (Fin n) := {a,b,x}
      have hp' : p ∈ P := hp
      have hxP : ∀ q ∈ P, x ∉ q := by
        intro q hq hqx
        apply hx
        exact Finset.mem_biUnion.mpr ⟨q,hq,hqx⟩
      have hxp : x ∉ p := hxP p hp'
  2. The vertices a and b are distinct (a ≠ b).

    Assume for contradiction that a = b. Then p = {a, b, c} is a subset of the two-element set {a, c}, meaning |p| ≤ |{a, c}| ≤ 2. But p is a 3-clique in G, so |p| = 3, yielding 3 ≤ 2, a contradiction.

    lines 15–24

    uses Finset.mem_insert, Finset.mem_singleton, Finset.card_le_card, Finset.card_le_two

      have hab : a ≠ b := by
        intro h
        have hs : p ⊆ ({a,c} : Finset (Fin n)) := by
          intro v hv
          simp only [p, Finset.mem_insert, Finset.mem_singleton] at hv ⊢
          aesop
        have hc := Finset.card_le_card hs
        have htwo := Finset.card_le_two (a := a) (b := c)
        have hp3 := (htri p hp').card_eq
        omega
  3. The candidate triangle t = {a, b, x} is not already an element of P.

    If t ∈ P, then because x ∈ t, x would belong to a triangle in P, contradicting the fact that x is outside the vertex support of P.

    lines 25–28

      have htP : t ∉ P := by
        intro ht
        have : x ∈ t := by simp [t]
        exact hxP t ht this
  4. Every element of the swapped packing Q = (P \ {p}) ∪ {t} is a 3-clique in G.

    Let R = P \ {p} and Q = {t} ∪ R. Any s ∈ Q is either t, which is a 3-clique by the hypothesis hface, or an element of R ⊆ P, which is a 3-clique by the assumption that every element of P is a 3-clique.

    lines 29–38

    uses Finset.mem_of_mem_erase, Finset.mem_insert.mp

      let R : Finset (Finset (Fin n)) := P.erase p
      let Q : Finset (Finset (Fin n)) := insert t R
      have hQt : t ∈ Q := by simp [Q]
      have hRsub : R ⊆ P := by intro q hq; exact Finset.mem_of_mem_erase hq
      have hface' : G.IsNClique 3 t := hface
      have hQtri : ∀ s ∈ Q, G.IsNClique 3 s := by
        intro s hs
        rcases Finset.mem_insert.mp hs with rfl | hs
        · exact hface'
        · exact htri s (hRsub hs)
  5. The triangle t intersects every other triangle q ∈ R in at most one vertex: |t ∩ q| ≤ 1.

    For any q ∈ R = P \ {p}, q belongs to P and q ≠ p, so pairwise edge-disjointness gives |p ∩ q| ≤ 1. Any vertex v ∈ t ∩ q must be in t = {a, b, x} and in q. Since x cannot belong to any triangle in P, v ≠ x, which forces v ∈ {a, b} ⊆ p. Therefore t ∩ q ⊆ p ∩ q, and taking cardinalities gives |t ∩ q| ≤ |p ∩ q| ≤ 1.

    lines 39–56

    uses Finset.ne_of_mem_erase, Finset.mem_inter.mp, Finset.mem_insert, Finset.mem_singleton, Or.inl, Or.inr, False.elim, Finset.mem_inter.mpr, Finset.card_le_card

      have htpair : ∀ q ∈ R, (t ∩ q).card ≤ 1 := by
        intro q hq
        have hqP : q ∈ P := hRsub hq
        have hne : p ≠ q := (Finset.ne_of_mem_erase hq).symm
        have hpq := hdisj hp' hqP hne
        have hsub : t ∩ q ⊆ p ∩ q := by
          intro v hv
          obtain ⟨hvt,hvq⟩ := Finset.mem_inter.mp hv
          have hvp : v ∈ p := by
            simp only [t, Finset.mem_insert, Finset.mem_singleton] at hvt
            simp only [p, Finset.mem_insert, Finset.mem_singleton]
            rcases hvt with rfl | rfl | rfl
            · exact Or.inl rfl
            · exact Or.inr (Or.inl rfl)
            · exact False.elim (hxP q hqP hvq)
          exact Finset.mem_inter.mpr ⟨hvp,hvq⟩
        have hc := Finset.card_le_card hsub
        omega
  6. The candidate packing Q is pairwise edge-disjoint.

    The subfamily R = P \ {p} is pairwise edge-disjoint as a subset of P. Adjoining t preserves this property because t shares at most one vertex with every member of R, and finset intersection cardinality is symmetric.

    lines 57–66

    uses Finset.coe_insert, Finset.inter_comm

      have hRpair : (R : Set (Finset (Fin n))).Pairwise (fun s u => (s ∩ u).card ≤ 1) := by
        intro s hs u hu hne
        exact hdisj (hRsub hs) (hRsub hu) hne
      have hQpair : (Q : Set (Finset (Fin n))).Pairwise (fun s u => (s ∩ u).card ≤ 1) := by
        change ((insert t R : Finset (Finset (Fin n))) : Set (Finset (Fin n))).Pairwise _
        rw [Finset.coe_insert]
        refine hRpair.insert ?_
        intro q hq _
        have hh := htpair q hq
        exact ⟨hh, by rw [Finset.inter_comm]; exact hh⟩
  7. The packing Q contains exactly as many triangles as P: |Q| = |P|.

    Since t ∉ P, t ∉ R, so inserting t into R gives |Q| = |R| + 1. Since p ∈ P, erasing p gives |R| = |P| - 1. Since P is nonempty (it contains p), |Q| = (|P| - 1) + 1 = |P|.

    lines 67–72

    uses Finset.card_insert_of_notMem, Finset.card_erase_of_mem, Finset.card_pos.mpr

      have hQcard : Q.card = P.card := by
        have htR : t ∉ R := fun h => htP (hRsub h)
        rw [show Q = insert t R by rfl, Finset.card_insert_of_notMem htR]
        rw [show R = P.erase p by rfl, Finset.card_erase_of_mem hp']
        have hpos : 0 < P.card := Finset.card_pos.mpr ⟨p,hp'⟩
        omega
  8. If some q ∈ P \ {p} contains c, then the vertex support of P is a subset of the vertex support of Q: V(P) ⊆ V(Q).

    Suppose some q ∈ P with q ≠ p contains c; then q ∈ R ⊆ Q. For any vertex v in the vertex support of P, v belongs to some triangle r ∈ P. If r ≠ p, then r ∈ R ⊆ Q, so v ∈ V(Q). If r = p = {a, b, c}, then: if v = a or v = b, v ∈ t ∈ Q; if v = c, v ∈ q ∈ Q since c ∈ q. In every case, v is covered by Q.

    lines 73–90

    uses Finset.mem_erase.mpr, Finset.mem_insert_of_mem, Finset.mem_biUnion.mp, Finset.mem_insert, Finset.mem_singleton, Finset.mem_biUnion.mpr

      intro q hq hqp hcq
      have hqR : q ∈ R := Finset.mem_erase.mpr ⟨hqp,hq⟩
      have hqQ : q ∈ Q := Finset.mem_insert_of_mem hqR
      have hsub : P.biUnion id ⊆ Q.biUnion id := by
        intro v hv
        obtain ⟨r,hr,hvr⟩ := Finset.mem_biUnion.mp hv
        by_cases hrp : r = p
        · subst r
          change v ∈ ({a,b,c} : Finset (Fin n)) at hvr
          simp only [Finset.mem_insert, Finset.mem_singleton] at hvr
          rcases hvr with rfl | rfl | rfl
          · exact Finset.mem_biUnion.mpr ⟨t,hQt,by simp [t]⟩
          · exact Finset.mem_biUnion.mpr ⟨t,hQt,by simp [t]⟩
          · exact Finset.mem_biUnion.mpr ⟨q,hqQ,hcq⟩
        · have hrR : r ∈ R := Finset.mem_erase.mpr ⟨hrp,hr⟩
          have hrQ : r ∈ Q := Finset.mem_insert_of_mem hrR
          exact Finset.mem_biUnion.mpr ⟨r,hrQ,hvr⟩
      have hxQ : x ∈ Q.biUnion id := Finset.mem_biUnion.mpr ⟨t,hQt,by simp [t]⟩
  9. The vertex support of Q is strictly larger than that of P, contradicting the maximality of P.

    We have V(P) ⊆ V(Q), and x ∈ t ∈ Q gives x ∈ V(Q), while x ∉ V(P). Hence V(P) ⊊ V(Q), so |V(P)| < |V(Q)|. However, Q is a valid edge-disjoint triangle packing of the same size as P, so by the support maximality of P, |V(Q)| ≤ |V(P)|. This contradiction shows that no triangle q ∈ P \ {p} can contain c.

    lines 91–99

    uses Finset.ssubset_iff_subset_ne.mpr, Finset.card_lt_card

      have hstrict : P.biUnion id ⊂ Q.biUnion id := by
        refine Finset.ssubset_iff_subset_ne.mpr ⟨hsub, ?_⟩
        intro heq
        apply hx
        rw [heq]
        exact hxQ
      have hlt := Finset.card_lt_card hstrict
      have hle := hsupport Q hQtri hQpair hQcard
      omega
Finset.mem_biUnion.mpr
An element belongs to the union of a family of finsets if and only if it belongs to at least one finset in the family (reverse implication).
Finset.mem_biUnion.mp
An element belongs to the union of a family of finsets implies it belongs to at least one finset in the family.
Finset.mem_insert
An element belongs to `insert b s` if and only if it equals `b` or belongs to `s`.
Finset.mem_insert.mp
If an element belongs to `insert b s`, then it either equals `b` or belongs to `s`.
Finset.mem_singleton
An element belongs to the singleton `{a}` if and only if it equals `a`.
Finset.card_le_card
If one finset is a subset of another, its cardinality is less than or equal to that of the other.
Finset.card_le_two
A finset with at most two listed elements has cardinality at most 2.
Finset.mem_of_mem_erase
If an element belongs to `s.erase a`, then it belongs to `s`.
Finset.ne_of_mem_erase
If an element belongs to `s.erase a`, then it is not equal to `a`.
Finset.mem_inter.mp
If an element belongs to the intersection of two finsets, it belongs to both.
Finset.mem_inter.mpr
If an element belongs to both finsets, it belongs to their intersection.
Or.inl
From a proof of A, infer A ∨ B.
Or.inr
From a proof of B, infer A ∨ B.
False.elim
From a contradiction (False), any conclusion follows.
Finset.coe_insert
Coercing an inserted finset to a set equals the set-theoretic insertion into the coerced set.
Finset.inter_comm
Intersection of finsets is commutative: s ∩ t = t ∩ s.
Finset.card_insert_of_notMem
Inserting an element not in a finset increases its cardinality by 1.
Finset.card_erase_of_mem
Erasing an element present in a finset decreases its cardinality by 1.
Finset.card_pos.mpr
A nonempty finset has strictly positive cardinality.
Finset.mem_erase.mpr
If b ≠ a and b ∈ s, then b ∈ s.erase a.
Finset.mem_insert_of_mem
If an element belongs to s, it belongs to insert b s.
Finset.ssubset_iff_subset_ne.mpr
If s ⊆ t and s ≠ t, then s is a strict subset of t (s ⊂ t).
Finset.card_lt_card
A strict subset of a finset has strictly smaller cardinality.

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_support_max_packing_outside_swap_private (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) (a b c x : Fin n) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hx : x ∉ P.biUnion id) (hface : G.IsNClique 3 ({a,b,x} : Finset (Fin n))) : ∀ q ∈ P, q ≠ ({a,b,c} : Finset (Fin n)) → c ∉ q := by  classical  let p : Finset (Fin n) := {a,b,c}  let t : Finset (Fin n) := {a,b,x}  have hp' : p ∈ P := hp  have hxP : ∀ q ∈ P, x ∉ q := by    intro q hq hqx    apply hx    exact Finset.mem_biUnion.mpr ⟨q,hq,hqx⟩  have hxp : x ∉ p := hxP p hp'  have hab : a ≠ b := by    intro h    have hs : p ⊆ ({a,c} : Finset (Fin n)) := by      intro v hv      simp only [p, Finset.mem_insert, Finset.mem_singleton] at hv ⊢      aesop    have hc := Finset.card_le_card hs    have htwo := Finset.card_le_two (a := a) (b := c)    have hp3 := (htri p hp').card_eq    omega  have htP : t ∉ P := by    intro ht    have : x ∈ t := by simp [t]    exact hxP t ht this  let R : Finset (Finset (Fin n)) := P.erase p  let Q : Finset (Finset (Fin n)) := insert t R  have hQt : t ∈ Q := by simp [Q]  have hRsub : R ⊆ P := by intro q hq; exact Finset.mem_of_mem_erase hq  have hface' : G.IsNClique 3 t := hface  have hQtri : ∀ s ∈ Q, G.IsNClique 3 s := by    intro s hs    rcases Finset.mem_insert.mp hs with rfl | hs    · exact hface'    · exact htri s (hRsub hs)  have htpair : ∀ q ∈ R, (t ∩ q).card ≤ 1 := by    intro q hq    have hqP : q ∈ P := hRsub hq    have hne : p ≠ q := (Finset.ne_of_mem_erase hq).symm    have hpq := hdisj hp' hqP hne    have hsub : t ∩ q ⊆ p ∩ q := by      intro v hv      obtain ⟨hvt,hvq⟩ := Finset.mem_inter.mp hv      have hvp : v ∈ p := by        simp only [t, Finset.mem_insert, Finset.mem_singleton] at hvt        simp only [p, Finset.mem_insert, Finset.mem_singleton]        rcases hvt with rfl | rfl | rfl        · exact Or.inl rfl        · exact Or.inr (Or.inl rfl)        · exact False.elim (hxP q hqP hvq)      exact Finset.mem_inter.mpr ⟨hvp,hvq⟩    have hc := Finset.card_le_card hsub    omega  have hRpair : (R : Set (Finset (Fin n))).Pairwise (fun s u => (s ∩ u).card ≤ 1) := by    intro s hs u hu hne    exact hdisj (hRsub hs) (hRsub hu) hne  have hQpair : (Q : Set (Finset (Fin n))).Pairwise (fun s u => (s ∩ u).card ≤ 1) := by    change ((insert t R : Finset (Finset (Fin n))) : Set (Finset (Fin n))).Pairwise _    rw [Finset.coe_insert]    refine hRpair.insert ?_    intro q hq _    have hh := htpair q hq    exact ⟨hh, by rw [Finset.inter_comm]; exact hh⟩  have hQcard : Q.card = P.card := by    have htR : t ∉ R := fun h => htP (hRsub h)    rw [show Q = insert t R by rfl, Finset.card_insert_of_notMem htR]    rw [show R = P.erase p by rfl, Finset.card_erase_of_mem hp']    have hpos : 0 < P.card := Finset.card_pos.mpr ⟨p,hp'⟩    omega  intro q hq hqp hcq  have hqR : q ∈ R := Finset.mem_erase.mpr ⟨hqp,hq⟩  have hqQ : q ∈ Q := Finset.mem_insert_of_mem hqR  have hsub : P.biUnion id ⊆ Q.biUnion id := by    intro v hv    obtain ⟨r,hr,hvr⟩ := Finset.mem_biUnion.mp hv    by_cases hrp : r = p    · subst r      change v ∈ ({a,b,c} : Finset (Fin n)) at hvr      simp only [Finset.mem_insert, Finset.mem_singleton] at hvr      rcases hvr with rfl | rfl | rfl      · exact Finset.mem_biUnion.mpr ⟨t,hQt,by simp [t]⟩      · exact Finset.mem_biUnion.mpr ⟨t,hQt,by simp [t]⟩      · exact Finset.mem_biUnion.mpr ⟨q,hqQ,hcq⟩    · have hrR : r ∈ R := Finset.mem_erase.mpr ⟨hrp,hr⟩      have hrQ : r ∈ Q := Finset.mem_insert_of_mem hrR      exact Finset.mem_biUnion.mpr ⟨r,hrQ,hvr⟩  have hxQ : x ∈ Q.biUnion id := Finset.mem_biUnion.mpr ⟨t,hQt,by simp [t]⟩  have hstrict : P.biUnion id ⊂ Q.biUnion id := by    refine Finset.ssubset_iff_subset_ne.mpr ⟨hsub, ?_⟩    intro heq    apply hx    rw [heq]    exact hxQ  have hlt := Finset.card_lt_card hstrict  have hle := hsupport Q hQtri hQpair hQcard  omega
See it in the graphDiscuss this resultChallenge it