AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_packing_insert_separated

theoremverified

A triangle sharing at most one vertex with every member of an edge-disjoint triangle packing can be inserted, increasing the packing size by one.

Statement

theorem simple_graph_triangle_packing_insert_separated
    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
    (P : Finset (Finset V)) (t : Finset V)
    (hp : ∀ s ∈ P, G.IsNClique 3 s)
    (hpp : (P : Set (Finset V)).Pairwise (fun s r => (s ∩ r).card ≤ 1))
    (ht : G.IsNClique 3 t)
    (hsep : ∀ s ∈ P, (s ∩ t).card ≤ 1) :
    (∀ s ∈ insert t P, G.IsNClique 3 s) ∧
    ((insert t P : Finset (Finset V)) : Set (Finset V)).Pairwise
      (fun s r => (s ∩ r).card ≤ 1) ∧
    (insert t P).card = P.card + 1
Source
Structural helper for the triangle packing-cover campaign; related matching-cover reductions are in https://arxiv.org/abs/2610.15269, Lemma 2.3. Finite checks and limitations are recorded in state/campaigns/triangle_reductions/high_codegree_route_in512.md.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

To add a triangle t sharing at most one vertex with every member of an edge-disjoint triangle packing P, the proof first establishes that t ∉ P: otherwise t would intersect itself in all 3 of its vertices, violating the separation hypothesis. The theorem then splits into three claims: every element of insert t P is a 3-clique, the elements remain pairwise edge-disjoint by the separation hypothesis and commutativity of intersection, and the packing cardinality increases by 1 because t ∉ P.

  1. The triangle t does not already belong to P (t ∉ P).

    Suppose for contradiction that t ∈ P. By the separation hypothesis hsep, t shares at most one vertex with every triangle in P, so |t ∩ t| ≤ 1. But t ∩ t = t by Finset.inter_self, and since t is a 3-clique, its cardinality is 3. This gives 3 ≤ 1, an arithmetic contradiction. Hence t ∉ P.

    lines 16–21

    uses Finset.inter_self

      classical
      have hnot : t ∉ P := by
        intro h
        have hh := hsep t h
        rw [Finset.inter_self, ht.card_eq] at hh
        omega
  2. Every element of insert t P is a 3-clique in G.

    We split the three-way conjunction into its constituent parts. For the first part, let s ∈ insert t P. By Finset.mem_insert.mp, either s = t or s ∈ P. If s = t, it is a 3-clique by the hypothesis ht; if s ∈ P, it is a 3-clique by the assumption hp on members of P.

    lines 22–26

    uses Finset.mem_insert.mp

      refine ⟨?_, ?_, ?_⟩
      · intro s hs
        rcases Finset.mem_insert.mp hs with rfl | hs
        · exact ht
        · exact hp s hs
  3. The collection insert t P is pairwise edge-disjoint, sharing at most one vertex between any two distinct members.

    We rewrite the finset insertion as a set insertion on coerced sets using Finset.coe_insert. Because P is already pairwise edge-disjoint (hpp), it suffices to show that t shares at most one vertex with every s ∈ P. The separation hypothesis hsep guarantees |s ∩ t| ≤ 1, and commutativity of intersection (Finset.inter_comm) ensures |t ∩ s| ≤ 1 as well.

    lines 27–31

    uses Finset.coe_insert, Finset.inter_comm

      · rw [Finset.coe_insert]
        refine hpp.insert ?_
        intro s hs _
        have hh := hsep s hs
        exact ⟨by rw [Finset.inter_comm]; exact hh, hh⟩
  4. The size of insert t P is |P| + 1.

    Because t ∉ P (established as hnot), inserting t into the finite set P increases its cardinality by 1: |insert t P| = 1 + |P| = |P| + 1, where addition is rearranged using Nat.add_comm.

    line 32

    uses Nat.add_comm

      · simp [hnot, Nat.add_comm]
Finset.inter_self
The intersection of any finite set with itself is the set itself: s ∩ s = s.
Finset.mem_insert.mp
If an element belongs to the insertion of an element a into a finite set s, it is either equal to a or belongs to s.
Finset.coe_insert
The set coercion of an element inserted into a finite set equals the set insertion into the coerced set.
Finset.inter_comm
Intersection of finite sets is commutative: s₁ ∩ s₂ = s₂ ∩ s₁.
Nat.add_comm
Addition of natural numbers is commutative: n + m = m + n.

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 Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem simple_graph_triangle_packing_insert_separated    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)    (P : Finset (Finset V)) (t : Finset V)    (hp : ∀ s ∈ P, G.IsNClique 3 s)    (hpp : (P : Set (Finset V)).Pairwise (fun s r => (s ∩ r).card ≤ 1))    (ht : G.IsNClique 3 t)    (hsep : ∀ s ∈ P, (s ∩ t).card ≤ 1) :    (∀ s ∈ insert t P, G.IsNClique 3 s) ∧    ((insert t P : Finset (Finset V)) : Set (Finset V)).Pairwise      (fun s r => (s ∩ r).card ≤ 1) ∧    (insert t P).card = P.card + 1 := by  classical  have hnot : t ∉ P := by    intro h    have hh := hsep t h    rw [Finset.inter_self, ht.card_eq] at hh    omega  refine ⟨?_, ?_, ?_⟩  · intro s hs    rcases Finset.mem_insert.mp hs with rfl | hs    · exact ht    · exact hp s hs  · rw [Finset.coe_insert]    refine hpp.insert ?_    intro s hs _    have hh := hsep s hs    exact ⟨by rw [Finset.inter_comm]; exact hh, hh⟩  · simp [hnot, Nat.add_comm]
See it in the graphDiscuss this resultChallenge it