simple_graph_pair_stable_kernel_link_edge_spoke_exchange
For an active outside vertex of a maximum packing supported in a support-plus-one-vertex kernel, the local edge/spoke exchange guaranteed by global two-edge stability has its witness vertices inside the kernel.
Statement
theorem simple_graph_pair_stable_kernel_link_edge_spoke_exchange (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) (a b w : Fin n) (hya : G.Adj y a) (hyb : G.Adj y b) (hab : G.Adj a b) (hyw : G.Adj y w) : ∃ u v : Fin n, u ∈ insert x (P.biUnion id) ∧ v ∈ insert x (P.biUnion id) ∧ G.Adj y u ∧ G.Adj y v ∧ G.Adj u v ∧ (u = a ∨ u = b ∨ v = a ∨ v = b) ∧ u ≠ w ∧ v ≠ w ∧ s(u,v) ≠ s(a,b)
- Source
- Exact local link transfer for the induced 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_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_pair_stable_vertex_link_edge_spoke_exchangeIn a two-edge-stable graph, for every edge yz of the link at x and every neighbor w of x, another link edge meets yz and avoids w.
- 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
To show that the exchange triangle guaranteed by two-edge stability around an outside vertex y stays inside the support-plus-one-vertex kernel {x} ∪ V(P), the proof first applies the local edge-spoke exchange lemma to obtain a new triangle {y, u, v}. Because Q is an alternate maximum triangle packing that does not contain y, any triangle containing y must lie entirely within {y} ∪ V(Q). Since both y and V(Q) are contained in {x} ∪ V(P), the witnesses u and v are forced to lie within the kernel.
There exist vertices u and v forming a triangle with y that shares a vertex with {a, b}, avoids the spoke w, and whose base edge is distinct from {a, b}.
By the global 2-edge stability hypothesis, removing any two distinct edges from G does not decrease its triangle packing number. We invoke the local vertex link edge-spoke exchange lemma at y for the triangle {y, a, b} and the incident edge yw, yielding vertices u and v adjacent to y and to each other such that {u, v} intersects {a, b}, neither u nor v is w, and {u, v} ≠ {a, b}.
uses
simple_graph_pair_stable_vertex_link_edge_spoke_exchangeclassical obtain ⟨u,v,hyu,hyv,huv,hmeet,huw,hvw,hne⟩ := simple_graph_pair_stable_vertex_link_edge_spoke_exchange n G y hstable a b w hya hyb hab hywThe three-element set {y, u, v} is a 3-clique (triangle) in G.
Because y, u, and v are pairwise adjacent in a simple graph (which has no self-loops), the vertices are pairwise distinct. A case analysis over all pairs of distinct elements in {y, u, v} confirms that every pair is adjacent, so {y, u, v} is indeed a 3-clique.
uses
Finset.mem_coe,Finset.mem_insert,Finset.mem_singleton,SimpleGraph.Adj.symmhave hneq1 : y ≠ u := hyu.ne have hneq2 : y ≠ v := hyv.ne have hneq3 : u ≠ v := huv.ne have ht : G.IsNClique 3 ({y,u,v} : Finset (Fin n)) := by constructor · intro r hr s hs hrs simp only [Finset.mem_coe,Finset.mem_insert,Finset.mem_singleton] at hr hs rcases hr with rfl | rfl | rfl <;> rcases hs with rfl | rfl | rfl all_goals first | contradiction | assumption | exact SimpleGraph.Adj.symm (by assumption) · simp [hneq1,hneq2,hneq3]
The entire triangle {y, u, v} is contained in the kernel {x} ∪ V(P).
Since |Q| = |P| = ν(G), the packing Q is a maximum triangle packing. Because y is outside the vertex support of Q, any triangle containing y must be contained in {y} ∪ V(Q). Since y is in {x} ∪ V(P) and the vertex support of Q is already a subset of {x} ∪ V(P), it follows that {y} ∪ V(Q) ⊆ {x} ∪ V(P), which places {y, u, v} inside the kernel.
uses
simple_graph_maximum_packing_outside_triangles_inside_support,Finset.insert_subset_iff.mprhave 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 {y,u,v} ht (by simp) have hsubW := hsub.trans (Finset.insert_subset_iff.mpr ⟨hy,hQsub⟩)
The vertices u and v provide the desired exchange witnesses inside the kernel.
Because {y, u, v} is contained in {x} ∪ V(P), both u and v belong to the kernel. Together with the adjacency, link intersection, spoke avoidance, and edge distinctness properties established in the first step, u and v satisfy all requirements of the theorem.
exact ⟨u,v,hsubW (by simp),hsubW (by simp),hyu,hyv,huv,hmeet,huw,hvw,hne⟩
simple_graph_pair_stable_vertex_link_edge_spoke_exchange- In a 2-edge-stable graph, given a triangle containing vertex x and another edge incident to x, there exists another triangle containing x that shares a vertex with the base of the first triangle, avoids the other incident edge, and does not share both base vertices.
Finset.mem_coe- An element belongs to the coercion of a finite set to a set if and only if it belongs to the finite set.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to the singleton set {a} if and only if it equals a.
SimpleGraph.Adj.symm- Adjacency in a simple graph is symmetric: if u is adjacent to v, then v is adjacent to u.
simple_graph_maximum_packing_outside_triangles_inside_support- If P is a maximum triangle packing and x lies outside the vertex support of P, then any triangle containing x is entirely contained in {x} ∪ V(P).
Finset.insert_subset_iff.mpr- If an element a belongs to t and a finite set s is a subset of t, then insert a s is also a subset of t.
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_kernel_link_edge_spoke_exchange (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) (a b w : Fin n) (hya : G.Adj y a) (hyb : G.Adj y b) (hab : G.Adj a b) (hyw : G.Adj y w) : ∃ u v : Fin n, u ∈ insert x (P.biUnion id) ∧ v ∈ insert x (P.biUnion id) ∧ G.Adj y u ∧ G.Adj y v ∧ G.Adj u v ∧ (u = a ∨ u = b ∨ v = a ∨ v = b) ∧ u ≠ w ∧ v ≠ w ∧ s(u,v) ≠ s(a,b) := by classical obtain ⟨u,v,hyu,hyv,huv,hmeet,huw,hvw,hne⟩ := simple_graph_pair_stable_vertex_link_edge_spoke_exchange n G y hstable a b w hya hyb hab hyw have hneq1 : y ≠ u := hyu.ne have hneq2 : y ≠ v := hyv.ne have hneq3 : u ≠ v := huv.ne have ht : G.IsNClique 3 ({y,u,v} : Finset (Fin n)) := by constructor · intro r hr s hs hrs simp only [Finset.mem_coe,Finset.mem_insert,Finset.mem_singleton] at hr hs rcases hr with rfl | rfl | rfl <;> rcases hs with rfl | rfl | rfl all_goals first | contradiction | assumption | exact SimpleGraph.Adj.symm (by assumption) · simp [hneq1,hneq2,hneq3] 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 {y,u,v} ht (by simp) have hsubW := hsub.trans (Finset.insert_subset_iff.mpr ⟨hy,hQsub⟩) exact ⟨u,v,hsubW (by simp),hsubW (by simp),hyu,hyv,huv,hmeet,huw,hvw,hne⟩