AFTD Auto-Formalizing Theoretical Domains

simple_graph_maximum_packing_outside_induced_kernel

theoremverified

The support of a maximum packing plus one vertex has at most three times the packing size plus one vertices and contains every triangle through any of its vertices outside any maximum packing supported within it.

Statement

theorem simple_graph_maximum_packing_outside_induced_kernel (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) : (insert x (P.biUnion id)).card ≤ 3 * P.card + 1 ∧ ∀ (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 ⊆ insert x (P.biUnion id) → ∀ y ∈ insert x (P.biUnion id), y ∉ Q.biUnion id → ∀ t : Finset (Fin n), G.IsNClique 3 t → y ∈ t → t ⊆ insert x (P.biUnion id)
Source
Proposed bounded induced model for outside links in state/campaigns/triangle_reductions/outside_induced_kernel_in701.md; no novelty claim.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

The theorem is proved in two parts. First, the extended support $\{x\} \cup \bigcup P$ has size at most $3|P| + 1$ because each of the $|P|$ triangles contains 3 vertices and the added vertex $x$ contributes at most 1. Second, any packing $Q$ of size $|P|$ is also maximum, so by a previously established lemma (`simple_graph_maximum_packing_outside_triangles_inside_support`), every triangle containing a vertex $y \notin \bigcup Q$ lies within $\{y\} \cup \bigcup Q$. Because both $y$ and the support of $Q$ are assumed to be subsets of $\{x\} \cup \bigcup P$, transitivity of set inclusion guarantees that the triangle is entirely contained in $\{x\} \cup \bigcup P$.

  1. It suffices to establish the cardinality bound and the triangle containment property separately.

    The theorem asserts a conjunction. Setting classical logic and applying `constructor` splits the proof into two independent goals: the upper bound on the cardinality of $\{x\} \cup \bigcup P$, and the containment of triangles through uncovered vertices.

    lines 2–3

      classical
      constructor
  2. The extended support $\{x\} \cup \bigcup P$ has cardinality at most $3|P| + 1$.

    Because each triangle in $P$ contains 3 vertices, the vertex support $\bigcup P$ contains at most $3|P|$ vertices (`Finset.card_biUnion_le_card_mul`). Inserting $x$ increases the set size by at most 1 (`Finset.card_insert_le`). Linear arithmetic over ℕ (`omega`) combines these bounds to conclude $|\{x\} \cup \bigcup P| \le 3|P| + 1$.

    lines 4–6

    uses Finset.card_biUnion_le_card_mul, Finset.card_insert_le

      · have h := Finset.card_biUnion_le_card_mul P id 3 (fun t ht => (htri t ht).card_eq.le)
        have h' := Finset.card_insert_le x (P.biUnion id)
        omega
  3. Any triangle containing an uncovered vertex of $\{x\} \cup \bigcup P$ is completely contained in $\{x\} \cup \bigcup P$.

    Let $Q$ be an edge-disjoint triangle packing of size $|P|$ whose vertices lie within $\{x\} \cup \bigcup P$. Since $|P|$ is the triangle packing number of $G$, $Q$ is also a maximum packing. For any vertex $y \in \{x\} \cup \bigcup P$ outside the support of $Q$ and any triangle $t$ containing $y$, the lemma `simple_graph_maximum_packing_outside_triangles_inside_support` shows that $t \subseteq \{y\} \cup \bigcup Q$. Since $y \in \{x\} \cup \bigcup P$ and $\bigcup Q \subseteq \{x\} \cup \bigcup P$, the set $\{y\} \cup \bigcup Q$ is a subset of $\{x\} \cup \bigcup P$ by `Finset.insert_subset_iff.mpr`. Transitivity of subset inclusion then yields $t \subseteq \{x\} \cup \bigcup P$.

    lines 7–10

    uses simple_graph_maximum_packing_outside_triangles_inside_support, Finset.insert_subset_iff.mpr

      · intro Q hQtri hQdisj hQcard hQsub y hy hynot t ht hyt
        have hQmax : Q.card = simple_graph_triangle_packing_number G := hQcard.trans hmax
        have hsub := simple_graph_maximum_packing_outside_triangles_inside_support n G Q hQtri hQdisj hQmax y hynot t ht hyt
        exact hsub.trans (Finset.insert_subset_iff.mpr ⟨hy,hQsub⟩)
Finset.card_biUnion_le_card_mul
The cardinality of the union of a finite collection of sets $s$ is at most $|s| \cdot n$ if every member set has cardinality at most $n$.
Finset.card_insert_le
Inserting an element into a finite set increases its cardinality by at most 1, so $|s \cup \{a\}| \le |s| + 1$.
simple_graph_maximum_packing_outside_triangles_inside_support
For any maximum edge-disjoint triangle packing $P$ and any vertex $x$ not covered by $P$, every triangle containing $x$ has all its vertices in $\{x\} \cup \bigcup P$.
Finset.insert_subset_iff.mpr
If $a \in s$ and $t \subseteq s$, then $\{a\} \cup t \subseteq 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_induced_kernel (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) : (insert x (P.biUnion id)).card ≤ 3 * P.card + 1 ∧ ∀ (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 ⊆ insert x (P.biUnion id) → ∀ y ∈ insert x (P.biUnion id), y ∉ Q.biUnion id → ∀ t : Finset (Fin n), G.IsNClique 3 t → y ∈ t → t ⊆ insert x (P.biUnion id) := by  classical  constructor  · have h := Finset.card_biUnion_le_card_mul P id 3 (fun t ht => (htri t ht).card_eq.le)    have h' := Finset.card_insert_le x (P.biUnion id)    omega  · intro Q hQtri hQdisj hQcard hQsub y hy hynot t ht hyt    have hQmax : Q.card = simple_graph_triangle_packing_number G := hQcard.trans hmax    have hsub := simple_graph_maximum_packing_outside_triangles_inside_support n G Q hQtri hQdisj hQmax y hynot t ht hyt    exact hsub.trans (Finset.insert_subset_iff.mpr ⟨hy,hQsub⟩)
See it in the graphDiscuss this resultChallenge it