simple_graph_pair_stable_outside_kernel_five_triangles
In a two-edge-stable graph, every active vertex that lies in the support-plus-one-vertex kernel and outside a maximum packing supported in that kernel has five distinct incident triangles inside the kernel.
Statement
theorem simple_graph_pair_stable_outside_kernel_five_triangles (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (P Q : Finset (Finset (Fin n))) (hPmax : P.card = simple_graph_triangle_packing_number G) (hQ : ∀ t ∈ Q, G.IsNClique 3 t) (hQdisj : (Q : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1)) (hQcard : Q.card = P.card) (x : Fin n) (hQsub : Q.biUnion id ⊆ insert x (P.biUnion id)) (hstable : ∀ e f : Sym2 (Fin n), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f → simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G) (y : Fin n) (hy : y ∈ insert x (P.biUnion id)) (hynot : y ∉ Q.biUnion id) (hactive : ∃ t : Finset (Fin n), G.IsNClique 3 t ∧ y ∈ t) : ∃ T : Finset (Finset (Fin n)), 5 ≤ T.card ∧ ∀ t ∈ T, G.IsNClique 3 t ∧ y ∈ t ∧ t ⊆ insert x (P.biUnion id)
- Source
- Outside-link finite model in state/campaigns/triangle_reductions/outside_induced_kernel_in701.md; no novelty claim.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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.
- simple_graph_pair_stable_active_vertex_at_least_five_trianglesIn a finite graph whose maximum triangle-packing number survives every two-edge deletion, any vertex that lies in a triangle lies in at…
- 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).
The proof, explained
The proof takes T to be the set of all triangles in G containing y. Because G is two-edge-stable and y is active, y belongs to at least five triangles, giving |T| ≥ 5. Furthermore, since Q is a maximum triangle packing not covering y, every triangle containing y has all its other vertices in the support of Q; because both y and the support of Q are contained in the kernel {x} ∪ ⋃ P, all five or more triangles in T lie entirely within the kernel.
There is a candidate set T of at least five triangles containing y, reducing the goal to showing that every triangle in T lies in the kernel {x} ∪ ⋃ P.
We define T to be the set of all triangles in G containing y. Because G is two-edge-stable and y is active (belongs to at least one triangle), lemma simple_graph_pair_stable_active_vertex_at_least_five_triangles implies that y belongs to at least five triangles, so |T| ≥ 5. Choosing T as the witness reduces the theorem to verifying that each t ∈ T is a triangle containing y whose vertices lie in {x} ∪ ⋃ P.
uses
simple_graph_pair_stable_active_vertex_at_least_five_trianglesclassical let T := (Finset.univ : Finset (Finset (Fin n))).filter (fun t => G.IsNClique 3 t ∧ y ∈ t) have hfive : 5 ≤ T.card := simple_graph_pair_stable_active_vertex_at_least_five_triangles n G y hstable hactive refine ⟨T,hfive,?_⟩
Every triangle t ∈ T containing y is contained in {y} ∪ ⋃ Q.
Let t ∈ T. By the definition of T (unpacked using Finset.mem_filter.mp), t is a triangle of G containing y. Since |Q| = |P| = ν(G), Q is also a maximum triangle packing. Because y is outside the vertex support of Q, lemma simple_graph_maximum_packing_outside_triangles_inside_support implies that the vertices of t must lie entirely within {y} ∪ ⋃ Q.
uses
Finset.mem_filter.mp,simple_graph_maximum_packing_outside_triangles_inside_supportintro t ht have ht' := (Finset.mem_filter.mp ht).2 have hQmax : Q.card = simple_graph_triangle_packing_number G := hQcard.trans hPmax have hsub := simple_graph_maximum_packing_outside_triangles_inside_support n G Q hQ hQdisj hQmax y hynot t ht'.1 ht'.2
Every triangle t ∈ T is contained in the kernel {x} ∪ ⋃ P, completing the proof.
By hypothesis, y ∈ {x} ∪ ⋃ P and the support ⋃ Q is a subset of {x} ∪ ⋃ P. Lemma Finset.insert_subset_iff.mpr shows that {y} ∪ ⋃ Q ⊆ {x} ∪ ⋃ P. Since t ⊆ {y} ∪ ⋃ Q, transitivity of inclusion yields t ⊆ {x} ∪ ⋃ P, completing the proof for all triangles in T.
uses
Finset.insert_subset_iff.mprexact ⟨ht'.1,ht'.2,hsub.trans (Finset.insert_subset_iff.mpr ⟨hy,hQsub⟩)⟩
simple_graph_pair_stable_active_vertex_at_least_five_triangles- In a two-edge-stable graph, any vertex incident to at least one triangle is incident to at least five distinct triangles.
Finset.mem_filter.mp- An element belongs to a filtered finite set only if it belongs to the ambient set and satisfies the predicate.
simple_graph_maximum_packing_outside_triangles_inside_support- Given a maximum triangle packing Q in a graph and a vertex y not covered by Q, any triangle containing y is entirely contained in {y} ∪ ⋃ Q.
Finset.insert_subset_iff.mpr- If an element a belongs to s and a finite set u is a subset of s, then {a} ∪ u is a subset of 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.
open scoped Sym2theorem simple_graph_pair_stable_outside_kernel_five_triangles (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (P Q : Finset (Finset (Fin n))) (hPmax : P.card = simple_graph_triangle_packing_number G) (hQ : ∀ t ∈ Q, G.IsNClique 3 t) (hQdisj : (Q : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1)) (hQcard : Q.card = P.card) (x : Fin n) (hQsub : Q.biUnion id ⊆ insert x (P.biUnion id)) (hstable : ∀ e f : Sym2 (Fin n), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f → simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G) (y : Fin n) (hy : y ∈ insert x (P.biUnion id)) (hynot : y ∉ Q.biUnion id) (hactive : ∃ t : Finset (Fin n), G.IsNClique 3 t ∧ y ∈ t) : ∃ T : Finset (Finset (Fin n)), 5 ≤ T.card ∧ ∀ t ∈ T, G.IsNClique 3 t ∧ y ∈ t ∧ t ⊆ insert x (P.biUnion id) := by classical let T := (Finset.univ : Finset (Finset (Fin n))).filter (fun t => G.IsNClique 3 t ∧ y ∈ t) have hfive : 5 ≤ T.card := simple_graph_pair_stable_active_vertex_at_least_five_triangles n G y hstable hactive refine ⟨T,hfive,?_⟩ intro t ht have ht' := (Finset.mem_filter.mp ht).2 have hQmax : Q.card = simple_graph_triangle_packing_number G := hQcard.trans hPmax have hsub := simple_graph_maximum_packing_outside_triangles_inside_support n G Q hQ hQdisj hQmax y hynot t ht'.1 ht'.2 exact ⟨ht'.1,ht'.2,hsub.trans (Finset.insert_subset_iff.mpr ⟨hy,hQsub⟩)⟩