simple_graph_maximum_packing_outside_triangles_inside_support
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
- 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_triangle_packing_edge_meetsEvery triangle shares an edge with a member of a maximum edge-disjoint triangle packing.
- Used by 3
- simple_graph_maximum_packing_outside_induced_kernelThe support of a maximum packing plus one vertex has at most three times the packing size plus one vertices and contains every triangle…
- simple_graph_pair_stable_outside_kernel_five_trianglesIn a two-edge-stable graph, every active vertex that lies in the support-plus-one-vertex kernel and outside a maximum packing supported in…
- simple_graph_pair_stable_kernel_link_edge_spoke_exchangeFor an active outside vertex of a maximum packing supported in a support-plus-one-vertex kernel, the local edge/spoke exchange guaranteed…
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.
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.
uses
simple_graph_maximum_triangle_packing_edge_meetsclassical obtain ⟨p,hp,hcount⟩ := simple_graph_maximum_triangle_packing_edge_meets G P htri hdisj hmax t htThe 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.
uses
Finset.mem_biUnion.mprhave hxp : x ∉ p := by intro h apply hx exact Finset.mem_biUnion.mpr ⟨p,hp,h⟩
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}.
uses
Finset.mem_inter.mp,Finset.mem_erase.mprhave 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⟩
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.
uses
Finset.card_erase_of_memhave hcard : (t.erase x).card = 2 := by have h := Finset.card_erase_of_mem hxt rw [ht.card_eq] at h omega
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.
uses
Finset.eq_of_subset_of_card_lehave heq : p ∩ t = t.erase x := Finset.eq_of_subset_of_card_le hsub (by omega)
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.
uses
Finset.mem_insert.mpr,Finset.mem_erase.mpr,Finset.mem_biUnion.mpr,Finset.mem_inter.mpintro 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
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_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⟩