simple_graph_maximum_packing_outside_induced_kernel
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
- simple_graph_triangle_packing_numberν(G): the maximum number of pairwise edge-disjoint triangles of G (two triangles are edge-disjoint when they share at most one vertex).
- simple_graph_maximum_packing_outside_triangles_inside_supportEvery triangle through a vertex outside a maximum triangle packing lies in that vertex together with the packing support.
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$.
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.
classical constructorThe 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$.
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
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$.
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$.
- In Lean, `P.biUnion id` represents the union of all triangles in the family $P$, which is the vertex support of the triangle packing $P$.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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⟩)