AFTD Auto-Formalizing Theoretical Domains

simple_graph_maximum_packing_outside_triangles_inside_support

theoremverified

Every triangle through a vertex outside a maximum triangle packing lies in that vertex together with the packing support.

Statement

theorem simple_graph_maximum_packing_outside_triangles_inside_support (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)) (hmax : P.card = simple_graph_triangle_packing_number G) (x : Fin n) (hx : x ∉ P.biUnion id) (t : Finset (Fin n)) (ht : G.IsNClique 3 t) (hxt : x ∈ t) : t ⊆ insert x (P.biUnion id)
Source
Elementary maximum-packing observation used in state/campaigns/triangle_reductions/outside_induced_kernel_in701.md; no novelty claim.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 3

The proof, explained

Because P is a maximum triangle packing, any triangle t in the graph shares an edge (at least two vertices) with some triangle p in P. Since x is outside the support of P, x cannot be in p, so all shared vertices must lie in t \\ {x}. But t has only 3 vertices, so t \\ {x} has only 2 vertices, forcing p ∩ t = t \\ {x}. Hence, every vertex of t other than x belongs to p (and therefore to the support of P), showing t ⊆ {x} ∪ ⋃ P.

  1. There exists a triangle p in the packing P that shares at least two vertices with t.

    Because P is a maximum triangle packing, any triangle t in G must share an edge (at least two vertices) with some triangle p ∈ P.

    lines 2–3

    uses simple_graph_maximum_triangle_packing_edge_meets

      classical
      obtain ⟨p,hp,hcount⟩ := simple_graph_maximum_triangle_packing_edge_meets G P htri hdisj hmax t ht
  2. The vertex x does not belong to p.

    By hypothesis, x does not belong to the support of P (the union of all sets in P). Since p ∈ P, if x were in p it would belong to the support, which is a contradiction.

    lines 4–7

    uses Finset.mem_biUnion.mpr

      have hxp : x ∉ p := by
        intro h
        apply hx
        exact Finset.mem_biUnion.mpr ⟨p,hp,h⟩
  3. The intersection p ∩ t is a subset of t \\ {x}.

    Any vertex y ∈ p ∩ t belongs to both p and t. Since x ∉ p, y cannot equal x, so y ∈ t \\ {x}.

    lines 8–12

    uses Finset.mem_inter.mp, Finset.mem_erase.mpr

      have hsub : p ∩ t ⊆ t.erase x := by
        intro y hy
        have hy' := Finset.mem_inter.mp hy
        apply Finset.mem_erase.mpr
        exact ⟨by intro h; subst y; exact hxp hy'.1,hy'.2⟩
  4. The set t \\ {x} has cardinality 2.

    Since t is a triangle, it has 3 vertices. Because x ∈ t, removing x leaves exactly 3 - 1 = 2 vertices.

    lines 13–16

    uses Finset.card_erase_of_mem

      have hcard : (t.erase x).card = 2 := by
        have h := Finset.card_erase_of_mem hxt
        rw [ht.card_eq] at h
        omega
  5. The intersection p ∩ t equals t \\ {x}.

    We have p ∩ t ⊆ t \\ {x}, |p ∩ t| ≥ 2, and |t \\ {x}| = 2. A subset of a finite set with at least as many elements as the superset must equal the superset.

    line 17

    uses Finset.eq_of_subset_of_card_le

      have heq : p ∩ t = t.erase x := Finset.eq_of_subset_of_card_le hsub (by omega)
  6. The triangle t is contained in {x} ∪ ⋃ P.

    For any vertex y ∈ t, either y = x (so y is the inserted vertex) or y ≠ x. In the latter case, y ∈ t \\ {x} = p ∩ t, so y ∈ p. Because p ∈ P, y lies in the union of the triangles in P.

    lines 18–24

    uses Finset.mem_insert.mpr, Finset.mem_erase.mpr, Finset.mem_biUnion.mpr, Finset.mem_inter.mp

      intro y hy
      by_cases hxy : y = x
      · subst y; simp
      · apply Finset.mem_insert.mpr
        right
        have hy' : y ∈ p ∩ t := by rw [heq]; exact Finset.mem_erase.mpr ⟨hxy,hy⟩
        exact Finset.mem_biUnion.mpr ⟨p,hp,(Finset.mem_inter.mp hy').1⟩
simple_graph_maximum_triangle_packing_edge_meets
In a graph with a maximum triangle packing P, every triangle shares at least two vertices with some triangle in P.
Finset.mem_biUnion.mpr
An element belongs to the union of a collection of sets if it belongs to at least one set in the collection.
Finset.mem_inter.mp
If an element belongs to the intersection of two sets, then it belongs to both sets.
Finset.mem_erase.mpr
If an element belongs to a set and is not equal to a given element, it belongs to the set with that element removed.
Finset.card_erase_of_mem
Removing an element that belongs to a finite set decreases its cardinality by one.
Finset.eq_of_subset_of_card_le
If a finite set s is a subset of t and |t| ≤ |s|, then s = t.
Finset.mem_insert.mpr
An element belongs to the insertion of b into a set s if it equals b or already belongs to s.

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

theorem simple_graph_maximum_packing_outside_triangles_inside_support (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)) (hmax : P.card = simple_graph_triangle_packing_number G) (x : Fin n) (hx : x ∉ P.biUnion id) (t : Finset (Fin n)) (ht : G.IsNClique 3 t) (hxt : x ∈ t) : t ⊆ insert x (P.biUnion id) := by  classical  obtain ⟨p,hp,hcount⟩ := simple_graph_maximum_triangle_packing_edge_meets G P htri hdisj hmax t ht  have hxp : x ∉ p := by    intro h    apply hx    exact Finset.mem_biUnion.mpr ⟨p,hp,h⟩  have hsub : p ∩ t ⊆ t.erase x := by    intro y hy    have hy' := Finset.mem_inter.mp hy    apply Finset.mem_erase.mpr    exact ⟨by intro h; subst y; exact hxp hy'.1,hy'.2⟩  have hcard : (t.erase x).card = 2 := by    have h := Finset.card_erase_of_mem hxt    rw [ht.card_eq] at h    omega  have heq : p ∩ t = t.erase x := Finset.eq_of_subset_of_card_le hsub (by omega)  intro y hy  by_cases hxy : y = x  · subst y; simp  · apply Finset.mem_insert.mpr    right    have hy' : y ∈ p ∩ t := by rw [heq]; exact Finset.mem_erase.mpr ⟨hxy,hy⟩    exact Finset.mem_biUnion.mpr ⟨p,hp,(Finset.mem_inter.mp hy').1⟩
See it in the graphDiscuss this resultChallenge it