AFTD Auto-Formalizing Theoretical Domains

simple_graph_maximum_triangle_packing_edge_meets

theoremverified

Every triangle shares an edge with a member of a maximum edge-disjoint triangle packing.

Statement

theorem simple_graph_maximum_triangle_packing_edge_meets
    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
    (P : Finset (Finset V))
    (hcl : ∀ t ∈ P, G.IsNClique 3 t)
    (hpair : (P : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1))
    (hsize : P.card = simple_graph_triangle_packing_number G) :
    ∀ t : Finset V, G.IsNClique 3 t → ∃ s ∈ P, 2 ≤ (s ∩ t).card
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
Built on 1
Used by 11

The proof, explained

The theorem is proved by contradiction: if a triangle t does not share an edge with any triangle in a maximum packing P, then t shares at most one vertex with each member of P. This implies that t ∉ P and that P ∪ {t} is itself an edge-disjoint triangle packing. But then |P ∪ {t}| = |P| + 1, contradicting the maximality of |P|.

  1. Suppose for contradiction that there exists a triangle t that shares at most one vertex with every triangle in P.

    We introduce an arbitrary triangle t in G and assume the negation of the conclusion. Pushing negations through the existential quantifier yields the hypothesis that for every triangle s ∈ P, |s ∩ t| < 2 (that is, s and t share at most one vertex, so they are edge-disjoint).

    lines 12–15

      classical
      intro t ht
      by_contra hno
      push_neg at hno
  2. The triangle t is not already in P (t ∉ P).

    If t were in P, our assumption would imply |t ∩ t| < 2. But t ∩ t = t and t is a 3-clique with 3 vertices, giving 3 < 2, a contradiction.

    lines 16–20

    uses Finset.inter_self

      have htP : t ∉ P := by
        intro htP
        have h := hno t htP
        rw [Finset.inter_self, ht.card_eq] at h
        omega
  3. Every element of P ∪ {t} is a triangle in G.

    Any element s ∈ P ∪ {t} is either t, which is a 3-clique by assumption, or an element of P, each of which is a 3-clique by the assumption that P is a triangle packing.

    lines 21–25

    uses Finset.mem_insert.mp

      have hp1 : ∀ s ∈ insert t P, G.IsNClique 3 s := by
        intro s hs
        rcases Finset.mem_insert.mp hs with rfl | hs
        · exact ht
        · exact hcl s hs
  4. The augmented family P ∪ {t} is pairwise edge-disjoint.

    The triangles in P are already pairwise edge-disjoint. For any s ∈ P, the contradictory hypothesis gives |s ∩ t| < 2, so |s ∩ t| ≤ 1 and, by symmetry of intersection, |t ∩ s| ≤ 1. Therefore, every pair of distinct triangles in P ∪ {t} shares at most one vertex.

    lines 26–32

    uses Finset.coe_insert, Finset.inter_comm

      have hp2 : ((insert t P : Finset (Finset V)) : Set (Finset V)).Pairwise
          (fun s t => (s ∩ t).card ≤ 1) := by
        rw [Finset.coe_insert]
        refine hpair.insert ?_
        intro s hs _
        have h := hno s hs
        exact ⟨by rw [Finset.inter_comm]; omega, by omega⟩
  5. The set A of sizes of all valid edge-disjoint triangle packings in G is bounded above.

    We define A ⊆ ℕ as the set of cardinalities of all pairwise edge-disjoint collections of triangles. Since each such collection is a finite subset of the finite set of all vertex subsets (Finset V), its size is bounded by the total number of subsets of V.

    lines 33–38

    uses Finset.card_le_univ

      let A : Set ℕ := {n | ∃ T : Finset (Finset V), (∀ a ∈ T, G.IsNClique 3 a) ∧
          (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ T.card = n}
      have hbound : BddAbove A := by
        refine ⟨Fintype.card (Finset V), ?_⟩
        rintro n ⟨T, _, _, rfl⟩
        exact Finset.card_le_univ T
  6. The cardinality |P ∪ {t}| is at most the triangle packing number of G.

    Because P ∪ {t} is a valid edge-disjoint triangle packing, its cardinality belongs to A. Since A is bounded above, its supremum is by definition the triangle packing number of G, which must be at least |P ∪ {t}|.

    lines 39–40

    uses le_csSup

      have hins : (insert t P).card ≤ simple_graph_triangle_packing_number G := by
        exact le_csSup hbound ⟨insert t P, hp1, hp2, rfl⟩
  7. A contradiction is reached: |P| + 1 ≤ |P|.

    Since t ∉ P, we have |P ∪ {t}| = |P| + 1. Substituting the hypothesis that |P| equals the triangle packing number into the inequality from the previous step yields |P| + 1 ≤ |P|, which is impossible.

    lines 41–42

    uses Finset.card_insert_of_notMem

      rw [Finset.card_insert_of_notMem htP, hsize] at hins
      omega
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, then it equals a or belongs to s.
Finset.coe_insert
Coercing an inserted finite set to a set equals inserting the element into the coerced set.
Finset.inter_comm
Intersection of finite sets is commutative: s₁ ∩ s₂ = s₂ ∩ s₁.
Finset.card_le_univ
The cardinality of any finite subset of a finite type is at most the cardinality of the whole type.
le_csSup
If a set in a conditionally complete lattice is bounded above, any element of the set is bounded by the supremum of the set.
Finset.card_insert_of_notMem
Inserting an element not already in a finite set increases the set's cardinality by 1.

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_maximum_triangle_packing_edge_meets    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)    (P : Finset (Finset V))    (hcl : ∀ t ∈ P, G.IsNClique 3 t)    (hpair : (P : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1))    (hsize : P.card = simple_graph_triangle_packing_number G) :    ∀ t : Finset V, G.IsNClique 3 t → ∃ s ∈ P, 2 ≤ (s ∩ t).card := by  classical  intro t ht  by_contra hno  push_neg at hno  have htP : t ∉ P := by    intro htP    have h := hno t htP    rw [Finset.inter_self, ht.card_eq] at h    omega  have hp1 : ∀ s ∈ insert t P, G.IsNClique 3 s := by    intro s hs    rcases Finset.mem_insert.mp hs with rfl | hs    · exact ht    · exact hcl s hs  have hp2 : ((insert t P : Finset (Finset V)) : Set (Finset V)).Pairwise      (fun s t => (s ∩ t).card ≤ 1) := by    rw [Finset.coe_insert]    refine hpair.insert ?_    intro s hs _    have h := hno s hs    exact ⟨by rw [Finset.inter_comm]; omega, by omega⟩  let A : Set ℕ := {n | ∃ T : Finset (Finset V), (∀ a ∈ T, G.IsNClique 3 a) ∧      (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ T.card = n}  have hbound : BddAbove A := by    refine ⟨Fintype.card (Finset V), ?_⟩    rintro n ⟨T, _, _, rfl⟩    exact Finset.card_le_univ T  have hins : (insert t P).card ≤ simple_graph_triangle_packing_number G := by    exact le_csSup hbound ⟨insert t P, hp1, hp2, rfl⟩  rw [Finset.card_insert_of_notMem htP, hsize] at hins  omega
See it in the graphDiscuss this resultChallenge it